URL：https://atcoder.jp/contests/abc293

目錄

E

Problem/題意

Thought/思路

Code/代碼

---

E

Problem/題意

給出 A、X、M，求?。

Thought/思路

一開始想等比數(shù)列求和，但是 m 不保證是質(zhì)數(shù)，所以不能用。

假設(shè) dp[x] 表示，前 x 個數(shù)求和的值。

• 當(dāng) x 為偶數(shù)時：dp[x] = dp[x / 2] + dp[x / 2] * ksm(a, x / 2)
• 當(dāng) x 為奇數(shù)時：dp[x] = 1 + a * dp[x - 1]

Code/代碼

不用記憶化也能過。

#include "bits/stdc++.h"#define int long longint a, x, m;
std::map <int, int> mp; // mp[x]：x 個數(shù)相加int ksm(int a, int b) {int res = 1;while (b > 0) {if (b & 1) res = res * a % m;b /= 2;a = a * a % m;}return res % m;
}int dfs(int x) {if (x == 1) return 1;if (x & 1) {mp[x - 1] = dfs(x - 1) % m;return (1 + a * mp[x - 1] % m) % m;} else {mp[x / 2] = dfs(x / 2) % m;return (mp[x / 2] + mp[x / 2] * ksm(a, x / 2) % m) % m;}
}signed main() {std::cin >> a >> x >> m;std::cout << dfs(x) % m;
}