-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其中m由小于 的素数组成p。

那么对于每个因子f都有的m因子1*f, p*f, p^2*f,...,p^e*f。n因此，所有因素的n乘积是

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

的所有因素f。m将因子的个数 asd和因子的乘积m作为ans组合公式的结果

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

现在可以递归地应用于素因子列表及其多重性。

于 2016-11-28T16:17:21.117 回答