爲什麼1從模中減去其中計算MOD = 1000000007

-2

問題的

的溶液

http://codeforces.com/contest/615/problem/D 鏈路是 http://codeforces.com/contest/615/submission/15260890

在以下代碼爲什麼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 ?? 
}

來源

2016-11-28 Shashi Kundan

因爲你沒有指出這段代碼應該做什麼，所以沒有人很可能知道這兩者。 – CollinD

現在，我添加解決方案和問題的鏈接 –

歡迎來到Stack Overflow！您可以閱讀如何[問]問題並創建[mcve]。這使我們更容易幫助你。 – Katie

除了這樣的事實，即代碼沒有多少意義，因爲它是不存在的，因爲它是費馬的小定理：

每當MOD是一個素數，如10^9+7是，一方面可以減少指數爲

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, ^2*f,...,p^e*f的因子n。以上的所有n因子的乘積因此是所有因素的mf將產物在

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

。推杆要素的號碼爲d和的m作爲ans結果因子的乘積組合式

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

現在可以被遞歸地應用於的素因子和它們的重數列表英寸

來源

2016-11-28 16:17:21 LutzL

爲什麼1從模中減去其中計算MOD = 1000000007

回答

相關問題