题解：AT_abc179_e [ABC179E] Sequence Sum

BLuemoon_ · 2024-09-15 21:42:07 · 题解

link

题意

定义 a_1=x,a_i=a_{i-1}^2\bmod m，求 \displaystyle\sum_{i=1}^{n}a_i。

思路

由于 m \le 10^5，a_i 的循环节至多为 10^5，于是我们可以暴力找出循环节并算出其的和。注意 x 并不一定在循环节中，需要特殊判断。最后把前面和后面剩余不在循环节的部分额外加上即可。

时间复杂度为 O(m)。

代码

// BLuemoon
#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using DB = double;

const int kMaxN = 2e5 + 5;

LL n, x, m, a[kMaxN], ans, cnt = 1, s, tmp, sum, k, p, cnt_;
map<LL, bool> v;
bool flag;
vector<LL> e;

void pr(bool pr) {
  cout << (pr ? "Yes" : "No") << '\n';
}

int main() {
  cin >> n >> x >> m, v[x] = 1, e.push_back(x);
  for (tmp = x * x % m; !v[tmp]; v[tmp] = 1, e.push_back(tmp), (tmp *= tmp) %= m) {
  }
  for (LL o : e) {
    if (flag == 0 && o != tmp) {
      ans += o, cnt_++;
      if (cnt_ == n) {
        cout << ans << '\n';
        return 0;
      }
    } else if (flag == 0 && o == tmp) {
      flag = 1, sum += o;
    } else if (flag) {
      sum += o, cnt++;
    }
  }
  ans += sum * ((n - cnt_) / cnt);
  for (LL i = cnt_ + 1 + (n - cnt_) / cnt * cnt; i <= n; i++, (tmp *= tmp) %= m) {
    ans += tmp;
  }
  cout << ans << '\n';
  return 0;
}