カブトムシ [yukicoder No.673]

https://yukicoder.me/problems/no/673

解法

https://yukicoder.me/submissions/251128

1日目はB
2日目はBC+B = B(C + 1)
3日目はBC^2 + BC + B = B(C^2 + C + 1)
よって、D日目は
B(C^(D - 1) + ... + C + 1) = B * (C ^ D - 1) / (C - 1)
で計算ができる。
C-1で割っているので、C=1のときだけ処理を分ける。
　
C=1の時は
1日目はB
2日目は2B
3日目は3B
よって、D日目はDBとなる。
　
あとは、上記の式を計算して答える。
割り算はフェルマーの小定理と繰り返し二乗法でやる。

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

    //mint ans = B * (C ^ D - 1) / (C - 1);

    if (C == 1) {
        mint ans = mint(B) * mint(D);
        cout << ans << endl;
        return;
    }

    mint ans = mint(B) * ((mint(C) ^ D) - 1) / mint(C - 1) * mint(C);
    cout << ans << endl;
}