本文主要是介绍【BZOJ 1951】 [Sdoi2010]古代猪文|数论|中国剩余定理|Lucas，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
搞清楚 费马小定理的适用条件
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int MO = 999911659;
const int MO1= 999911658;
int t[5]={0,2,3,4679,35617};
int a[5];
int F(int x,int p,int P)
{if(p==0) return 1;int tmp=F(x,p/2,P);tmp=(LL)tmp*tmp%P;if(p&1) tmp=(LL)tmp*x%P;return tmp;
}
int C(int n,int m,int P)
{int x=1,y=1;for(int i=1;i<=m;i++){y=(LL)y*i%P;x=(LL)x*(n-i+1)%P;}return (LL)x*F(y,P-2,P)%P;
}
int Lacus(int n,int m,int P)
{if(m==0) return 1;return (LL)Lacus(n/P,m/P,P)*C(n%P,m%P,P)%P;
}
int Solve()
{int ans=0;for(int i=1;i<=4;i++)ans=(ans+(LL)a[i]*(MO/t[i])%MO1*F(MO/t[i],t[i]-2,t[i])%MO1)%MO1;return ans;
}
int main()
{int n,g;cin >>n >>g;if(g==MO) {cout <<0;return 0;}for(int i=1,tmp=sqrt(n);i<=tmp;i++)if(n%i==0)for(int j=1;j<=4;j++){a[j]=(a[j]+Lacus(n,i,t[j]))%t[j];if(i*i!=n)a[j]=(a[j]+Lacus(n,n/i,t[j]))%t[j];}cout <<F(g,Solve(),MO);return 0;
}
这篇关于【BZOJ 1951】 [Sdoi2010]古代猪文|数论|中国剩余定理|Lucas的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
