---

擴展歐拉定理

\[a^k=a^{k\mod \varphi(p)+\varphi(p)}\ \ \ (mod\ p)\]

讓后發現\(\varphi(p)\)不是質數不能求逆元

\[999911659=2\times 3\times 4679\times35617\]

分別用lucas定理求完以后再用中國剩余定理合并一下就行

---

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define M 1000001 #define LL long long using namespace std;LL n,m,g,A[M],B[M],inv[M],k,ans1,ans2,ans3,ans4,p=999911658;LL C(LL x,LL y,LL p) {if(y>x) return 0;if(x<p && y<p) return A[x]*B[y]%p*B[x-y]%p;return C(x/p,y/p,p)*C(x%p,y%p,p)%p; }LL solve(LL p) {LL ans=0; A[0]=B[0]=inv[1]=1;for(int i=2;i<p;i++) inv[i]=(p-p/i)*inv[p%i]%p;for(int i=1;i<p;i++) A[i]=A[i-1]*i%p;for(int i=1;i<p;i++) B[i]=B[i-1]*inv[i]%p;for(int i=1;i<=m;i++) if(n%i==0) ans=(ans+C(n,i,p)+C(n,n/i,p))%p;if(m*m==n) ans=(ans-C(n,m,p)+p)%p;return ans; }LL ksm(LL x,LL y,LL p) {LL z=1;for(;y>1;y>>=1, x=x*x%p) if(y&1) z=z*x%p;return z*x%p; }int main() {scanf("%lld%lld",&n,&g); m=sqrt(n);ans1=solve(2)*(p/2)%p; ans4=solve(35617)*(p/35617)%p*ksm(p/35617,35615,35617)%p; ans3=solve(4679)*(p/4679)%p*ksm(p/4679,4677,4679)%p; ans2=solve(3)*(p/3)%p*(p/3%3)%p; m=(ans1+ans2+ans3+ans4)%p;printf("%lld",ksm(g,m+p,p+1)); }

轉載于:https://www.cnblogs.com/ZUTTER/p/10371467.html

總結

以上是生活随笔為你收集整理的[Sdoi2010]古代猪文的全部內容，希望文章能夠幫你解決所遇到的問題。

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