描述

=>G∑(ni),i|nmodP

---

分析

• k=∑Cin,i|n(modP)
• G?(P)≡1(modP),?(p)=p?1
• P′=P?1=>GP′≡1(modP)
• Gk≡GkmodP′(modP)
• 如何求k?
• lucas定理(nm)=(nmodP′mmodP′)?(n/P′m/P′)
• P’不是素數, lucas定理不適用.
• 所以把P'-1拆成2*3*4679*35617再用中國剩余定理來解.
• 一下子用這么多不熟悉的定理和方法感覺這個題好厲害.

• 終于知道當被模的數不是質數該怎么用中國剩余定理處理了.

• 這個題里的中國剩余定理的逆元運算可以用擴展歐幾里得也可以直接用歐拉定理. 我偏向后者, 因為快速冪是無論如何也要打的.

• 當 g == mod 的時候輸出應為0

• 這是因為當 g == mod 的時候費馬小定理不適用

---

代碼

https://code.csdn.net/snippets/634512

#include <cstdio> using namespace std; typedef long long lli;const int maxn = 40000; const lli mod = 999911658; const lli factor[] = {2, 3, 4679, 35617};lli A[4]; lli fac[4][maxn];lli pow_mod(lli n, lli m, lli p) {n %= p;lli ret = 1;for(; m; m>>=1, n = n*n % p)if(m & 1) ret = ret*n % p;return ret; }lli inv(lli n, lli p) {return pow_mod(n, p-2, p); }lli C(lli n, lli m, int i) {if(n < m) return 0;return fac[i][n] * inv(fac[i][m]*fac[i][n-m], factor[i]); }lli lucas(lli n, lli m, int i) {if(m == 0) return 1;lli p = factor[i];return lucas(n/p, m/p, i) * C(n%p, m%p, i) % p; }lli CRT() {lli m = mod, x = 0;for(int i = 0; i < 4; i++) {lli w = m / factor[i];x = (x + inv(w, factor[i]) * A[i] * w) % m;}return (x + m) % m; }int main() {lli n, m, g;scanf("%lld %lld", &n, &g);if(mod+1 == g) return puts("0"), 0;for(int i = 0; i < 4; i++) {fac[i][0] = 1;for(int j = 1; j <= factor[3]; j++)fac[i][j] = fac[i][j-1] * j % factor[i];}for(m = 1; m*m <= n; m++) if(n % m == 0)for(int i = 0; i < 4; i++) {A[i] = (A[i] + lucas(n, m, i)) % factor[i];if(m*m != n) A[i] = (A[i] + lucas(n, n/m, i)) % factor[i];}printf("%lld\n", pow_mod(g, CRT() % mod, mod+1));return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的BZOJ-1951-古代猪文-SDOI2010-费马小定理+欧拉函数+lucas定理+中国剩余定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。