门票 简单的循环

门票

Description

RPK要带MSH去一个神秘的地方！
RPK带着MSH穿过广场，在第1618块砖上按下了一个按钮，在一面墙上随即出现了一个把手。RPK握住把手，打开了一扇石质大门。他们穿过悠长而芬芳的小道，走到了一扇象征时间的大门——“the gate of time”。
门上写着一个关于时间的谜题“承诺：____年”，RPK思考了一会，从容地用手指写下了1万，这时，门开始发出闪光，MSH感觉到自己的心跳都快停止了。
门开了，眼前是一座美丽的神秘花园！
正当RPK和MSH准备进入的时候，突然出现了一个看门的老大爷QL。
QL：“你们干什么，还没买票呢！”
RPK突然想起来现金全拿去买蛋糕了，RPK很绅士地问：“能刷卡么？我身上没现金。”
QL：“没钱？那你们不能进去！”
RPK（汗）：“……”
QL：“等等，我这有道不会解的数学题，你解了我就让你们进去。”
（众人：“……”）
有一个数列{a_n}，a₀=1，a_i+1=(A×a_i+a_i mod B) mod C，要求这个数列第一次出现重复的项的标号。
这点小问题当然难不倒数学bug男RPK了，仅凭心算他就得到了结果。

Input

一行三个数，分别表示A,B,C

Output

输出第一次出现重复项的位置，如果答案超过2 000 000，输出-1

Sample Input

2 2 9

Sample Output

4

Description

对于30%的数据，A,B,C≤10⁵。
对于100%的数据，A,B,C≤10⁹。
对于100%的数据，空间限制4M。

分析题目，显然我们可以知道，这个数列必然存在一个循环节。
假如它并不是一个循环数列，那么它必然有无数个不同的整数。
但因为数列的递推过程中有取模操作，也就是说，该数列可以出现的整数必然是有限的。
所以对于一个无穷的数列来说，它不可能存在有限个不同整数且使它们不重复出现。
那么显然，它必然会进入一个循环。
因此，我们只需要找到这个循环节的长度，并且不断比较某个数和循环节长度加上该数后的数，观察是否能够相等即可。

当然，循环节的长度我们通过题目所给的第2000000个数向后延伸求取，如果这样无法求到一个相同的数来构成循环，那么我们可以知道循环节长度过大，答案应该是-1.
所以，我们可以打出如下代码。

#include <cstdio>

#define LL long long 

using namespace std;

LL a,b,c,d=-1,now=1,k;

int main()
{
	scanf("%lld%lld%lld",&a,&b,&c);
	for (register int i=1;i<=2000000;i++)
	{
		now=(a*now+now%b)%c;
		if (now==1)
			return printf("%d",i),0;
	}
	k=now;
	for (register int i=1;i<=2000000;i++)
	{
		now=(a*now+now%b)%c;
		if (now==k)
		{
			d=i;
			break;
		}
	}
	if (d<0)
		return printf("-1"),0;
	now=1;
	for (register int i=1;i<=d;i++)
		now=(a*now+now%b)%c;
	k=1;
	for (register int i=1;i+d<=2000000;i++)
	{
		now=(a*now+now%b)%c;
		k=(a*k+k%b)%c;
		if (now==k)
		{
			if (i+d>2000000)
				return printf("-1"),0;
			else
				return printf("%lld",(LL )i+d),0;
		}
	}
	return printf("-1"),0;
}