为什么在计算中mod where mod =1000000007 减去1

Question

link 个问题

http://codeforces.com/contest/615/problem/D link 的解决方案是 http://codeforces.com/contest/615/submission/15260890

在下面的代码中，我无法理解为什么从 mod 中减去 1 其中 mod=1000000007

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 ??
}

Answer 1

除了代码在上下文之外没有多大意义之外，还有费马小定理:

每当 MOD 是质数时，如 10^9+7 是，可以将指数减少 (MOD-1) 的倍数，因为任何 a 不是 [= 的倍数14=]

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

也就是说

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

至于代码，对于它的任务是有效的，考虑 n=m*p^e 其中 m 由小于 p 的素数组成。

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

的乘积

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

超过 m 的所有因素 f。将因子数设为 d，将 m 的因子乘积设为 ans，得到组合公式

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

现在可以递归地应用于素数及其重数列表。

为什么在计算中mod where mod =1000000007 减去1

why 1 is subtracted from mod where mod =1000000007 in calculation

math

primes

numbers

number-theory

mod