难度： 绿左右

算法： 数学，哈希

给出一个正常的做法，不知道有没有数学做法。

下文中记 $a_i$ 为数列第 $i$ 项，再令 $n=2\times 10^6$。

观察到，对于正整数 $i$，$a_i$ 的值仅与 $a_{i-1}$ 和一堆事先给定的常数有关。所以如有 $a_i=a_j$ ，则有 $a_{i+p}=a_{j+p}$。显然的，这个数列将在一个数以后构成循环。记循环节长度为 $k$。

求循环节：

对于 $a_n$，如有一个最大的 $i$ 使得 $a_i=a_n$ ，则 $n-i$ 为循环节。如果找不到这样的 $i$ ，则无解。很显然，如果找得到循环节，那么一定有解。

判断第一个出现两次的数：

直接找最小的 $i>k$ 使得 $a_i=a_{i-k}$ 即可。

代码如下，时间复杂度 $O(n)$，空间复杂度 $O(1)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c,x=1,y=1,k=-1,p,e=1,n=2e6;
ll ne(ll s){//下一项
	return (a*s+s%b)%c;
}
int main(){
	scanf("%lld%lld%lld",&a,&b,&c);
	for(ll i=1;i<=n;i++) e=ne(e);//求末项 
	for(ll i=0;i<n;i++){//求循环节 
		if(!i) p=1;
		else p=ne(p);
		if(p==e) k=max(k,i);
	}
	if(k<0){//没有循环节就无解，退出 
		printf("-1");
		return 0;
	}
	k=n-k;
	for(ll i=1;i<=n;i++){//求第一个重复项 
		y=ne(y);
		if(i>=k){
			if(x==y){
				printf("%lld",i);
				return 0;
			}
			x=ne(x);
		}
	}
}