题目：ABC179E - Sequence Sum
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/AT_abc179_e
- 参考题解：https://www.luogu.com.cn/problem/solution/AT_abc179_e
- 标签：
数学
题解
思路
- 前置知识：（a * b) mod m = [ (a mod m) * (b mod m) ] mod m
- 首先n的数据量相当大，又是做乘方运算，直接暴力模拟是不现实的
- 所以我们可以通过前置知识中的定理去找它余数的循环节，然后通过循环节的和以及n去推导最终答案
代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
typedef long long LL;
void best_coder() {
LL n, m, x;
scanf("%lld%lld%lld", &n, &x, &m);
vector<int> cnt(m 5);
vector<LL> ans (m 5);
int c = 1;
LL l, r;
LL i;
for (i = x ; ; c) {
if (cnt[i] == 0) {
cnt[i] = c;
} else {
l = cnt[i];
r = c - 1;
break;
}
ans[c] = ans[c - 1] i;
i = (i * i) % m;
}
LL len = r - l 1;
LL sum = ans[min(n, l - 1)];
n = max(0ll, n - l 1);
if (n > 0) {
sum = (ans[r] - ans[l - 1]) * (n / len) (ans[n % len l - 1] - ans[l - 1]);
}
printf("%lld", sum);
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 返回
return 0;
}
代码学习
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int LOG = 35;
int main(){
long long N;
int X, M;
cin >> N >> X >> M;
vector<vector<int>> next(35, vector<int>(M));
for (int i = 0; i < M; i ){
next[0][i] = (long long) i * i % M;
}
for (int i = 1; i < LOG; i ){
for (int j = 0; j < M; j ){
next[i][j] = next[i - 1][next[i - 1][j]];
}
}
vector<vector<long long>> sum(35, vector<long long>(M));
for (int i = 0; i < M; i ){
sum[0][i] = i;
}
for (int i = 1; i < LOG; i ){
for (int j = 0; j < M; j ){
sum[i][j] = sum[i - 1][j] sum[i - 1][next[i - 1][j]];
}
}
long long ans = 0;
for (int i = 0; i < LOG; i ){
if (N >> i & 1){
ans = sum[i][X];
X = next[i][X];
}
}
cout << ans << endl;
}
END
