Codeforces 359C - Prime Number
問題文
Prime Number概要
を素数とする.
を とするとき(ここで), mod を求めよ.
解法
明らかに答えは のべきとなる. 具体的には, とすると が答えとなりそうだが, が の倍数個あるとするとそれらは 個まとめることで 個にすることができる.
このようにまとめていく作業はたかだか でできるが, ある の個数を求めるのには 時間の処理(ソートとかstd::map とか) が必要なので全体の計算量は である.
コード
#include <cstdio> #include <vector> #include <algorithm> #define MOD (1000000007) using namespace std; typedef long long lint; lint pow(lint a, lint n) { lint ret = 1, b = a; while (n){ if (n & 1) ret = (ret * b) % MOD; b = (b * b) % MOD; n >>= 1; } return (ret); } int main() { int n; int x; lint sum = 0; vector<lint> a; scanf("%d %d", &n, &x); for (int i = 0; i < n; i++){ int y; scanf("%d", &y); a.push_back(y); sum += y; } for (int i = 0; i < n; i++) a[i] = sum - a[i]; sort(a.rbegin(), a.rend()); while (1){ lint target = a[a.size() - 1]; int cnt = 0; while (a.size() && a[a.size() - 1] == target){ ++cnt; a.pop_back(); } if (cnt % x){ printf("%lld\n", pow(x, target)); break; } else { for (int i = 0; i < cnt / x; i++) a.push_back(target + 1); } } return (0); }