はまやんはまやんはまやん

hamayanhamayan's blog

等比数列 [第三回 アルゴリズム実技検定 C]

https://atcoder.jp/contests/past202005-open/tasks/past202005_c

前提知識

  • 繰り返し二乗法

解説

https://atcoder.jp/contests/past202005-open/submissions/14066469

(公式解説見たら、解説の方がよっぽどいい方針でした。そちらがオススメ)
自分の解法はライブラリ貼るだけで終わりそうだったので、それでやった解法です。

まず、一番厳しい問題としてオーバーフローがある。
A=R=N=109という最大ケースを考えると、普通に第N項を計算しようとすると、
C++で楽に扱える1018はゆうに越えてしまう。
pythonとかの多倍長整数が扱えれば大丈夫かもしれないが、このサイズ感はどうなんだろう(よくわからない)。
この問題を解決する上で少し重要なことなのだが、A, AR, AR2, ...としていったときに広義単調増加となる。
つまり、ある地点で109より大きければ、それ以降はずっと大きくなる。
なので、計算過程である値より大きい値が出てきても、ある限界値でトリムしても大丈夫なことになる。

何を言ってるか分からないかもしれないので、具体例を出す。
計算に上限値を設けるということだ。
上限値を100として、10×20は200だけど上限100なので、100と計算する。
これで上限値を109+1としてやれば、最終的な結果が109+1以上であれば、
実際の計算結果がそれ以上であることはあまり問題ではなく、「large」が答えになる。

ll mul(ll a, ll b) { if (a == 0) return 0; if (infl / a < b) return infl; return min(infl, a * b); }
自分は、infl(1018くらい)を上限値として掛け算する関数をライブラリとして持ってるので使った。

さて、上限付き掛け算を使うことでオーバーフロー対策ができることは分かった。
これを使って、ARN-1を計算して109を越えているかどうかを判定できればよさそうだ。

A×はいいとして、RN-1を高速に計算することが求められる。
これには繰り返し二乗法を使用する。
累乗計算の高速化として有名なので、どこかで学んできてほしい。
まあ、学んでしまえばもう終わりで、掛け算している所を上の上限付き掛け算にするだけで終わり。

int A, R, N;
int MA = 1e9;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> R >> N;

    ll an = mul(A, fastpow(R, N - 1));
    if (MA < an) cout << "large" << endl;
    else cout << an << endl;
}