AtCoder ABC #179 : E - Sequence Sum

これは定番かな。
https://atcoder.jp/contests/abc179/tasks/abc179_e

問題

整数X,Mに対し、

• A[1]=X
• A[i+1]=A[i]*A[i]%M

で定義される整数列を考える。
最初のN項の総和を求めよ。

解法

数列の値が直前の値で決まるので、周期はM以下である。
そこで先頭M要素ぐらい求めれば、途中で周期的なパターンに入るので、同じパターンを繰り返している部分は繰り返し回数分をまとめて処理しよう。

ll N,X,M;
int pre[201010];
ll A[201010],S[201010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>M;
	MINUS(pre);
	A[1]=S[1]=X;
	pre[X]=1;
	int start,loop;
	for(i=2;i<=201010;i++) {
		A[i]=(A[i-1]*A[i-1])%M;
		S[i]=S[i-1]+A[i];
		
		if(i==N) {
			cout<<S[i]<<endl;
			return;
		}
		
		if(pre[A[i]]>=0) {
			start=pre[A[i]];
			loop=i-pre[A[i]];
			break;
		}
		pre[A[i]]=i;
	}
	
	ll ret=0;
	ll lp=(N-start)/loop;
	ret+=lp*(S[start+loop]-S[start]);
	N-=lp*loop;
	ret+=S[N];
	cout<<ret<<endl;
	
	
}

まとめ

変なミスをして手間取ってしまった。