大きな指数を使用した (a^b)%MOD の計算

このコーディング チャレンジでは、タスクは pow( a、b)%MOD。指数 b は非常に大きくなる可能性があります。従来の log(b) 時間計算量法は小さい値には適していますが、 b が C の long long データ型の容量を超えると実用的ではなくなります。

ただし、より効率的なアプローチにはオイラーのトーティエント関数を活用する必要があります。 φ(MOD)。オイラーの定理では、a^φ(MOD)≡1(mod MOD) となります。これは、a のべき乗が a^(b % φ(MOD)) に大幅に削減できることを意味します。

φ(MOD) の計算自体は簡単な作業ではありませんが、整数因数分解方法を使用して達成できます。 。計算後、指数 b を b % φ(MOD) に置き換えることで、計算時間を大幅に短縮できます。

さらなる改良

2008 年に、シュラムは φ が次のことを実証しました。 (b) は、i の範囲が 1 から b である場合、gcd(b, i) の離散フーリエ変換から取得できます。これにより、明示的な因数分解の必要がなくなります。

さらに、カーマイケルの関数 λ(MOD) を使用すると、特に a と MOD が共通の因数を共有する場合に、正しい答えを得ることができます。

コードの実装

次のコード スニペットは、C での例として機能します。 :

#include 
#include 

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }

ll pmod(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    if (b % 2 == 1) {
        return (a * pmod(a, b - 1, mod)) % mod;
    } else {
        ll tmp = pmod(a, b / 2, mod);
        return (tmp * tmp) % mod;
    }
}

int main() {
    ll a, b, mod;
    cin >> a >> b >> mod;
    cout