题意
定义 \(f(x,m)= x \bmod m\)。
有一个序列 \(a\)，满足 \(a_1=1\)，\(a_i=f(a_{i-1}^2,m)\)。
求
\[\sum_{i=1}^na_i \]思路
这道题 \(n\) 的数据范围很大，但 \(m\) 最多只有 \(10^5\)，因此考虑以此为突破口。
需要用到如下的同余性质：
\[(a \times b) \bmod m = (a \bmod m \times b \bmod m) \bmod m \]证明过程不详解。
有了这条性质，我们可以得知，当某个余数第二次出现时，则意味着出现了“循环节”（因为其再继续运算下去的结果也与先前一样）。因此，我们可以暴力计算前面的 \(a_i\)，同时找出“循环节”，找到即可终止循环。
接下来，我们要将序列分割为三部分计算。
-
“循环节”前非循环节部分
-
完整的一段一段的“循环节”
-
尾部不完整的“循环节”
具体实现详见代码。
Code
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int pd[1000001],sum[1000001];
int ans,x,n,m,len,w,s;
signed main()
{
cin >> n >> x >> m;
for( int i = 1 ; true ; i++,x = x * x % m)
{
if(pd[x])
{
len = i - pd[x];
w = pd[x];
break;
}
else pd[x] = i;
sum[i] = sum[i-1] + x;
}
ans = min ( n , w - 1 );
ans = sum[ans]; //非循环节部分
if( w < n )
{
s = n - w + 1;
ans += ( sum[w + len - 1] - sum[w - 1] ) * (s / len );//完整的一段一段的“循环节”
ans += sum[w - 1 + s % len] - sum[w - 1];//尾部不完整的“循环节”
}
cout << ans;
return 0;
}