題意：計(jì)算?
從外往里分析:
0. p=999911659是素?cái)?shù).所以先判斷G%p是否為0的情況,不為0說(shuō)明gcd(G,p)=1 接著往下走
1.互質(zhì)則使用歐拉函數(shù)對(duì)這個(gè)冪次進(jìn)行降冪.即，但是這兒對(duì)大組合數(shù)的和取的模不是質(zhì)數(shù),所以要借用ExLucass的思想,不過(guò)這兒不能用這個(gè)擴(kuò)展的盧卡斯,它的復(fù)雜度遠(yuǎn)比盧卡斯定理的復(fù)雜度高出很多.
2.lucass:把(合數(shù))模數(shù)分解質(zhì)因子pi，每個(gè)pi下的 算出.對(duì)應(yīng)的所有的pi算完之后,用crt解同余方程就合并出了G的冪次，用快速冪搞一下就行了.
#include <bits/stdc++.h>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
#pragma comment(linker, "/STACK:1024000000,1024000000")
void ex_gcd(int a, int b, int &d, int &x, int &y) { if (!b) { x = 1; y = 0; d = a; } else { ex_gcd(b, a%b, d, y, x); y -= x * (a / b); }; }
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int lcm(int a,int b){return a/gcd(a,b)*b;}//只適用于a,b 2者的情況
int inv_exgcd(int a, int m) { int d, x, y;ex_gcd(a, m, d, x, y);return d == 1 ? (x + m) % m : -1; }
typedef long long ll;
const int maxn=1e6;
using namespace std;
ll fac[maxn];
ll a,b,Mod=999911659,mod;
int r[5];
int primer[]={2,3,4679,35617};
ll Pow(ll a,ll n,ll mod)
{ll ans=1;while(n){if(n&1)ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;
}
void init()
{fac[0]=1;for(int i=1;i<=mod;++i)fac[i]=fac[i-1]*i%mod;
}
ll C(ll n,ll m,ll mod)
{if(m>n)return 0;ll ans=fac[n];ans*=inv_exgcd((fac[m]*fac[n-m])%mod,mod);return ans%mod;
}
ll Lucas(ll n,ll m,ll mod)
{if(m==0)return 1;return C(n%mod,m%mod,mod)*Lucas(n/mod,m/mod,mod)%mod;
}
ll crt(int n,int *c,int *m){ll M=1,ans=0;for(int i=0;i<n;++i) M*=m[i];
for(int i=0;i<n;++i) ans=(ans+M/m[i]*c[i] %M *inv_exgcd(M/m[i],m[i]))%M; return ans;}
void solve(ll n,ll G)
{memset(r,0,sizeof(r));for(int k=0;k<4;++k){mod=primer[k],init();for(ll i=1;i*i<=n;++i)///暴力求解，不知道有沒(méi)有O(1)的公式去求出{if(n%i==0){r[k]=(r[k]+Lucas(n,i,primer[k]))%primer[k];if(i*i!=n)r[k]=(r[k]+Lucas(n,n/i,primer[k]))%primer[k];}}}// r數(shù)組就是所得的余數(shù), primer為模數(shù),用crt合并解出最終的結(jié)果 ll ans=crt(4,r,primer);ans=Pow(G,ans,Mod);printf("%lld\n",ans);
}
int main()
{ll G,n;while(scanf("%lld%lld",&n,&G)!=EOF){if(G%Mod==0){printf("0\n");continue;}G%=Mod;solve(n,G);}return 0;
}
雖說(shuō)改出來(lái)的2個(gè)T到飛，也是改出來(lái)的啊:
殺雞不是不可以用宰牛刀,可是你想過(guò)雞的感受嘛><
#include <iostream>//Lucas模板
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
const int maxn=1e5;
const int MOD=999911658;
using namespace std;
void ex_gcd(ll a, ll b, ll &d, ll &x, ll &y) { if (!b) { x = 1; y = 0; d = a; } else { ex_gcd(b, a%b, d, y, x); y -= x * (a / b); }; }
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int lcm(int a,int b){return a/gcd(a,b)*b;}//?è3yoó3?·àò?3?
ll inv_exgcd(ll a, ll m) { ll d, x, y;ex_gcd(a, m, d, x, y);return d == 1 ? (x + m) % m : -1; }
ll cnt=0;
int primer[5]={2,3,4679,35617};
ll A[5];
ll Pow(ll a,ll n,ll mod)
{ll ans=1;while(n){if(n&1)ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;
}
ll C(ll n,ll p,ll pk)
{if(n==0)return 1;ll ans=1;for(ll i=2;i<=pk;++i)if(i%p)ans=ans*i%pk;ans=Pow(ans,n/pk,pk);for(ll k=n%pk,i=2;i<=k;++i)if(i%p)ans=ans*i%pk;return ans*C(n/p,p,pk)%pk;
}
ll ex_lucas(ll n,ll m,ll p,ll pi,ll pk)
{ll i,j,k=0,a,b,c,ans;a=C(n,pi,pk),b=C(m,pi,pk),c=C(n-m,pi,pk);for(i=n;i;i/=pi)k+=i/pi;for(i=m;i;i/=pi)k-=i/pi;for(i=n-m;i;i/=pi)k-=i/pi;ans=a*inv_exgcd(b,pk)%pk*inv_exgcd(c,pk)%pk*Pow(pi,k,pk)%pk;return ans*(p/pk)%p*inv_exgcd(p/pk,pk)%p;中國(guó)剩余定理 a[i]*M*x 余數(shù)*其他個(gè)個(gè)素?cái)?shù)的乘積*x
}
void solve(ll G,ll n)
{if(G%(MOD+1)==0){printf("0\n");return;}G%=MOD+1;ll ans=0;for(int i=0;i<4;++i){for(ll j=1;j*j<=n;++j){if(n%j==0){ans=(ans+ex_lucas(n,j,MOD,primer[i],primer[i]))%MOD;if(j*j!=n)ans=(ans+ex_lucas(n,n/j,MOD,primer[i],primer[i]))%MOD;}}}ans%=MOD;ans=Pow(G,ans,MOD+1);printf("%lld\n",ans);
}
int main()
{//IO;ll n,G;scanf("%lld%lld",&n,&G);//cin>>n>>G;solve(G,n);return 0;
}
?
總結(jié)
以上是生活随笔為你收集整理的HYSBZ-1951 古代猪文 【好题】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
