warum 1 von mod subtrahiert wobei mod = 1000000007 bei der Berechnung

Question

Link Frage

http://codeforces.com/contest/615/problem/D Link Lösung http://codeforces.com/contest/615/submission/15260890

Im folgenden Code ist zu verstehen, ich bin nicht in der Lage, warum von mod subtrahiert 1 wo 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

Abgesehen von der Tatsache, dass es der Code nicht viel Sinn macht, wie aus dem Zusammenhang, wie es ist, da das ist kleinen Satz von Fermat:

Wenn MOD eine Primzahl ist, wie 10^9+7 ist, kann man Exponenten als

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

reduzieren, was bedeutet, dass

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

---

In Bezug auf die Code, der für seine Aufgabe effizient ist, betrachten n=m*p^e wo m ist bestehend aus Primzahlen kleiner als .

Dann gibt es für jeden Faktor f von m Faktoren 1*f, p*f, ^2*f,...,p^e*f von n. Das Produkt über alle Faktoren von n ist somit das Produkt über

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

über alle Faktoren f von m. Setzt man die Zahlen von Faktoren wie d und das Produkt von Faktoren von m als ans Ergebnissen in der kombinierten Formel

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

die nun rekursiv in der Liste der Primfaktoren und ihre Multiplizitäten angewandt werden.