Many Powers [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/many-powers

解説

https://www.hackerrank.com/contests/75th/challenges/many-powers/submissions/code/1321980113

今回の問題の弱点はCが小さいことである。

例えば、(1³ + 2³ + 3³ + 4³ + 5³ + 6³ + 7³) % 3を計算しようと考えたときに、
mod 3上では、4³ = 1³となるので、全部0³～2³に変換できる。
よって、(2 * 0³ + 3 * 1³ + 2 * 2³) % 3を計算できればいいことになる。

解法としては、0～C-1を全探索する。
i^Bとなる個数を計算したいが、倍数の個数を計算しているようなものなので、単純な割り算で計算可能。
あとは、個数×i^Bの総和をmod Cでやれば答え。

ll A, B, C;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C;

    mod = C;

    int ans = 0;
    rep(i, 0, C) {
        ll cnt = A / C;
        if (0 < i && i <= A % C) cnt++;
        ans = add(ans, mul(cnt % C, modpow(i, B)));
    }
    cout << ans << endl;
}