題意：

給定q ，n? 求$q^{\sum\limits {d|n} C_{n}^ze8trgl8bvbq }mod 999911659$

題解：

首先如果你直接算次方上的數(shù)的話會(huì)炸掉，因?yàn)闅W拉定理我們可以得到

$q^{\sum\limits {d|n} C_{n}^ze8trgl8bvbq mod999911658}mod 999911659$

因?yàn)閙od的數(shù)是個(gè)合數(shù)

我們嘗試分解質(zhì)因數(shù) $999911658=2\times 3\times 4679\times 35617$

遇到這種式子不要急著$ex_lucas$，觀察性質(zhì)，$999911658 $中分解的數(shù)都為$1$次

所以我們可以直接用$lucas$求出來$mod$ $2$，$3$，$4679$，$35617$下各自的值，最后中國(guó)剩余定理合并即可

具體實(shí)現(xiàn)看代碼

代碼：

#include<bits/stdc++.h> #define ll long long #define A 40000 ll a[A],b[A],k,p,n; ll w[6]={0,2,3,4679,35617,999911659}; ll jie[5][A],ni[5][A]; ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll gcd=exgcd(b,a%b,x,y);ll t=x;x=y;y=t-a/b*y;return gcd; } ll meng(ll x,ll k,ll cix){ll ans=1;for(;k;k>>=1,x=x*x%w[cix])if(k&1)ans=ans*x%w[cix];return ans; } ll china(){ll x,y,a=0,m,n=1;for(ll i=1;i<=4;i++)n*=w[i];for(ll i=1;i<=4;i++){m=n/w[i];exgcd(w[i],m,x,y);a=(a+y*m*b[i])%n;}if(a>0) return a;return a+n; } ll jic(ll n,ll m,ll cix){if(m>n) return 0;if(m==0) return 1; // printf("jie=%lld ni=%lld ni2=%lld n=%lld m=%lld\n",jie[cix][n],ni[cix][n-m],ni[cix][m],n,m);return jie[cix][n]%w[cix]*ni[cix][n-m]%w[cix]*ni[cix][m]%w[cix]; } ll lucas(ll n,ll m,ll cix){if(n==0)return 1; // printf("jic=%lld n=%lld m=%lld cix=%lld n=%lld m=%lld\n",jic(n%w[cix],m%w[cix],cix),n%w[cix],m%w[cix],cix,n,m);return jic(n%w[cix],m%w[cix],cix)*lucas(n/w[cix],m/w[cix],cix)%w[cix]; } using namespace std; int main() {scanf("%lld%lld",&n,&p);if(n==999911659){cout<<0<<endl;return 0;}for(ll i=1;i<=4;i++){jie[i][0]=1;ni[i][0]=1;for(ll j=1;j<w[i];j++)jie[i][j]=jie[i][j-1]*j%w[i];ni[i][w[i]-1]=meng(jie[i][w[i]-1],w[i]-2,i); // printf("jie=%lld ni=%lld\n",jie[i][w[i]-1],ni[i][w[i]-1]);for(ll j=w[i]-2;j>=1;j--){ni[i][j]=ni[i][j+1]*(j+1)%w[i]; //if(j>=35600) printf("ni[%lld][%lld]=%lld\n",i,j,ni[i][j]); }for(ll j=1;j*j<=n;j++){if((n%j)==0){ // printf("luc=%lld i=%lld j=%lld\n",lucas(n,j,i),i,j);(b[i]+=lucas(n,j,i))%=w[i]; if(j*j!=n){(b[i]+=lucas(n,n/j,i))%=w[i];}} // printf("b[%lld]=%lld j=%lld\n",i,b[i],j);// printf("b[%lld]=%lld j=%lld\n",i,b[i],j); }} // for(ll i=1;i<=4;i++) // printf("%lld\n",b[i]);ll j=china(); // cout<<j<<endl;ll k=meng(p,china(),5);cout<<k<<endl;//模w「i」 剩余b「i」 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/znsbc-13/p/11233285.html

總結(jié)

以上是生活随笔為你收集整理的古代猪文的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。