思路:
式子最后有个modC,故数列中任意项取值范围为[0,C)
当项数足够多时一定会有重复的项,所以当检查到2e^6都还没找到重复的项时,直接输出-1即可
所以实际上我们需要做的就是:
检验a[0]~a[2e6]是否存在重复的项,否则输出-1
我们知道哈希表是一种把大的值域映射到小的集合的数据结构,因而用哈希表来存储数据在查找数据上具有很大优势
这里我采用的拉链法构造哈希表,每一步要做的就是:如果在哈希表里查不到和a[i]相同的项,便插入a[i],直至找到相同的项或者下标>2e^6
下面是代码
C++ 代码
#include<iostream>
#include<cstring>//包含memset()函数
using namespace std;
typedef long long LL;
const int N=2e6+10,P=1e5+3;
int h[N];
LL e[N],ne[N],idx=0;
//现在处理第idx个节点,e[idx]为这个节点的值,ne[idx]为这个节点的下一个点的下标
LL A,B,C;
void insert(LL x)//往里面插入x
{
int k=(x%P+P)%P;//确保哈希值非负
e[++idx]=x;
ne[idx]=h[k];
h[k]=idx;
}
bool find(LL x)//找哈希表里是否有x
{
int k=(x%P+P)%P;
for(int i=h[k];i!=-1;i=ne[i])
{
//找到了
if(e[i]==x) return true;
}
return false;
}
int main()
{
cin>>A>>B>>C;
//初始化哈希表,-1标记这个位置还没插入值
memset(h,-1,sizeof h);
LL a=1;//初始值
int i=0;//i表示我现在插入a[i]
bool fact=false;
while(i<=2e6&&!fact) //结束循环的条件有两种:要么是现在的数的下标来到了2e6+1还没找到,要么是已经找到了
{
if(!find(a))
{
insert(a);
a=(A*a+a%B)%C;
}
else
{
cout<<i;
fact=true;
}
i++;
}
//如果是还没找到,则输出-1
if(!fact) cout<<"-1";
return 0;
}