傳送門

文章目錄

• 題目描述
• 解析
• 總結
• 代碼

題目描述

解析

簡單來說，就是求：

g^{∑C(d,n)(d是n的約數）}mod 999911659

可以先特判一下，999911659|g時，答案為0
否則，可以通過歐拉定理轉化為：

g^{∑C(d,n)(d是n的約數）mod999911658} mod 999911659

取完模之后，指數已經限制在了一個較小的范圍，如果求出其值，就可以用快速冪解決
現在考慮求這個指數：

∑C(d,n)(d是n的約數）mod999911658

面對這樣較大的組合數取模，容易想到用盧卡斯定理解決
但是問題在于本題的模數太大
所以我們考慮對這個模數進行質因數分解：

999911658=234679*35617

如果對這四個模數分別取模，就能把模數限制在一個可以接受的大小，并建立出4個同余方程
然后再利用中國剩余定理，解出這個指數即可

總結

本題的關鍵在于遇見大模數后進行質因數分解在進行中國剩余定理的轉化

代碼

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define ll long long #define int long long const int N=3e5+100; const ll mod=999911658; const ll Mod=999911659; ll ksm(ll x,ll o){ll ans=1,res=x%Mod;while(o){if(o&1) ans=(ans*res)%Mod;res=(res*res)%Mod;o>>=1;}return ans%Mod; } ll n; ll g; ll m[5]={0,2,3,4679,35617},M[5],MM,t[5]; ll d[N],num; void divide(ll x){int top=floor(sqrt(x));d[++num]=1;for(int i=2;i<=top;i++){if(x%i==0){d[++num]=i;if(n/i!=i) d[++num]=n/i;}}d[++num]=x;return; } ll ni[5][N],jc[N]; ll a[5];ll C(int k,ll d,ll n){if(d>n) return 0;if(d==n) return 1;return (jc[n]*ni[k][d]*ni[k][n-d])%m[k]; } ll lucas(int k,ll d,ll n){if(d==n) return 1;if(d>n) return 0;return (C(k,d%m[k],n%m[k])%m[k])*lucas(k,d/m[k],n/m[k])%m[k]; } void gcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return;}gcd(b,a%b,x,y);int o=y;y=x-a/b*y;x=o;y%=mod;x%=mod; } signed main(){scanf("%lld%lld",&n,&g);if(g%Mod==0) {printf("0");return 0;}divide(n);jc[0]=jc[1]=1;for(int i=1;i<=4;i++) ni[i][0]=ni[i][1]=1;for(int i=2;i<=35167;i++){jc[i]=(jc[i-1]*i)%mod;for(int j=1;j<=4;j++) ni[j][i]=((m[j]-m[j]/i)*ni[j][m[j]%i])%m[j];}for(int i=2;i<=35167;i++) for(int j=1;j<=4;j++)ni[j][i]=(ni[j][i]*ni[j][i-1])%m[j];for(int i=1;i<=num;i++){for(int j=1;j<=4;j++){a[j]=(a[j]+lucas(j,d[i],n))%m[j];//printf("d=%lld mod=%lld ans=%lld\n",d[i],m[j],lucas(j,d[i],n)%m[j]);}}MM=mod;ll ans=0;for(int i=1;i<=4;i++){M[i]=MM/m[i];ll o;gcd(M[i],m[i],t[i],o);ans+=(t[i]*M[i]*a[i])%mod;ans%=mod;} // for(int j=1;j<=4;j++){ // printf("k=%d mod=%d:\n",j,m[j]){ // for(int i=1;i<=num;i++){ // printf // } // } // }ans%=MM;while(ans<0) ans+=MM;printf("%lld\n",ksm(g,ans)%Mod);return 0; } /* 4 5 1 5 2 7 3 4 2 */

總結

以上是生活随笔為你收集整理的洛谷P2480:古代猪文（中国剩余定理）（欧拉定理）的全部內容，希望文章能夠幫你解決所遇到的問題。

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