这题就是个组合数而已hh..
C(n,m)=C(n,n-m).然后就是最多sqrt(n)解决吧~还是水题舒服.
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=999911659; const ll N=2e3; ll yz[N]; ll qp(ll a,ll b) { ll res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } ll C(ll a,ll b) { if(b>a-b) b=a-b; ll res=1,ans=1; for(ll i=2;i<=b;i++) res=res*i%mod; ll lv=qp(res,mod-2); for(int i=a;i>a-b;i--) { ans=ans*i%mod; } return ans*lv%mod;//=ans*lv%mod; } int main() { ll n,q,g=0; cin>>n>>q; for(ll i=1;i*i<=n;i++) { if(n%i==0) {yz[g++]=i;if(i!=n/i) yz[g++]=n/i;} } ll res=0; for(ll i=0;i<g;i++) { res+=C(n,yz[i]); // cout<<yz[i]<<' '<<C(n,yz[i])<<endl; } ll ans=qp(q,res); cout<<ans<<endl; return 0; }
被打脸了,呜呜呜...
仔细想想处理确实不对,因为q^p%mod!=q^(p%mod)%mod.
下面讲正解:
题目要求: q^p % mod.
mod是质数,由费马小定理可知q^(mod-1)%mod=1.然后就是求q^(p%(mod-1))%mod.因为组合数p很大会爆,所以要进行取模运算.但是组合数取模又存在/数问题,非质数逆元可求,但是不保证p和mod-1互质,这个就很麻烦了.做法还是有,exlucas..hh其实不用,做法就是把mod-1进行质因子分解出来4个数分别是:2 3 4679 35617.令p%(mod-1)=x.p%2=b1.p%3=b2.p%4679=b3.p%35617=b4.下面就是4个方程了.
x%2=b1. x%3=b2. x%4679=b3. x%35617=b4.
用中国剩余定理解出x即可.中国剩余定理前面博客已经有了.
然后lucas大家知道模板就行了hh,证明以后变强了再看.
然后代码如下:
ll lucas(ll n,ll m) { if(m==0) return 1; else return (ll)lucas(n/p,m/p)*c(n%p,m%p)%p; }
ac代码如下:
// 2 3 4679 35617 #include <bits/stdc++.h> using namespace std; typedef long long ll; //const ll mod=999911659; ll a[4]={2,3,4679,35617};//模数 ll b[4];//余数 ll m[4]; ll t[4]; ll qp(ll aa,ll bb,ll mod) { ll res=1; while(bb) { if(bb&1) res=res*aa%mod; aa=aa*aa%mod; bb>>=1; } return res; } ll C(ll n,ll m,ll mod) { if(m>n) return 0; if(n-m<m) m=n-m; ll res=1; for(ll i=n;i>n-m;i--) { res=res*i%mod; } ll sum=1; for(ll i=m;i>=2;i--) { sum=sum*i%mod; }sum=qp(sum,mod-2,mod); return res*sum%mod; } ll lucas(ll n,ll m,ll mod) { if(m==0) return 1; else return lucas(n/mod,m/mod,mod)*C(n%mod,m%mod,mod)%mod; } ll get(ll x,ll n) { ll res=0; for(ll i=1;i*i<=n;i++) { if(n%i==0) { res=(res+lucas(n,i,x))%x; if(i*i==n) continue; res=(res+lucas(n,n/i,x))%x; } } return res; } int main() { ll n,q; cin>>n>>q; ll M=999911659ll-1ll; if(q==M+1ll) {puts("0"); return 0;} //得到他们的lucas b[0]=get(a[0],n);b[1]=get(a[1],n);b[2]=get(a[2],n);b[3]=get(a[3],n); for(ll i=0;i<4;i++) m[i]=M/a[i]; for(ll i=0;i<4;i++) { t[i]=qp(m[i],a[i]-2,a[i]); } ll ans=0; for(int i=0;i<4;i++) { ans+=t[i]*m[i]*b[i]; } cout<<qp(q,ans,999911659ll)<<endl; return 0; }