-2

質問のリンク

http://codeforces.com/contest/615/problem/D ソリューションのリンクは http://codeforces.com/contest/615/submission/15260890です

以下のコードでは、mod=1000000007 の mod から 1 が減算される理由を理解できません。

ll d = 1;
ll ans = 1;
for (auto x : cnt) {
    ll cnt = x.se;
    ll p = x.fi;
    ll fp = binPow(p, (cnt + 1) * cnt / 2, MOD);
    ans = binPow(ans, (cnt + 1), MOD) * binPow(fp, d, MOD) % MOD;
    d = d * (x.se + 1) % (MOD - 1);//why ??
}
4

1 に答える 1

3

コードがあるという事実は別として、文脈から外れているほど意味がありませんが、フェルマーの小さな定理があります。

MODが素数である場合はいつでも10^9+7、指数を の倍数で減らすことができ(MOD-1)ますa。MOD

a ^ (MOD-1) == 1  mod MOD.

つまり、

a^b == a ^ (b mod (MOD-1))  mod MOD.

そのタスクにとって効率的なコードに関しては、 がより小さい素数で構成されているn=m*p^e場所を考えてみましょう。mp

次に、 の因子ごとに の因子がfありmます。したがってのすべての要素の積は、上の積です。1*f, p*f, p^2*f,...,p^e*fnn

p^(0+1+2+...+e) * f^(e+1) = p^( e*(e+1)/2 ) * f^(e+1)

のすべての要因fについてm。因数の数 asとasdの因数の積を入れると、結合された式が得られますmans

ans = ans^( e+1 ) * p^( d*e*(e+1)/2 )
d = d*(e+1)

これは、素因数とその多重度のリストに再帰的に適用できるようになりました。

于 2016-11-28T16:17:21.117 に答える