相应题目链接：https://vjudge.net/contest/175786#overview
1.线性筛选素数：参考http://blog.csdn.net/zhang20072844/article/details/7647763
#include N 100000+5 int prime[N]; bool s[N]; void Prime() { int i,j,k,t; //判断是否素数 for (i=2; i<=N; i+=2) s[i]=0; for (i=1; i<=N; i+=2) s[i]=1; s[1]=0; s[2]=1; for (i=3; i<=sqrt(N); i+=2) { if (s[i]) { k=2*i;//应为所有偶数已经剔除，所以此处t=3*i（相当于）也就是此次剔除的仍是奇数，所以避免了重复剔除偶数，速度快。 t=i+k; while (t<=N) { s[t]=0; t=t+k; } } } //素数打表 k=1; prime[1]=2; for (i=3; i<=N; i+=2) { if (s[i]==1) { k++; prime[k]=i; } } }2.快速幂： int pow(int a,int b) { int ans=1; while(b) { if(b&1) ans=ans*a; a=a*a; b=b>>1; } return ans; }3.欧几里德gcd+求乘法逆元x：（ax+by=c//ax=c+by）通解 x = x0 + (b/gcd)*t y = y0 - (a/gcd)*t
int e_gcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int gcd=e_gcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return gcd; } int main() { int x,y,c; cin>>a>>b; //ax+by=c gcd=e_gcd(a,b,x,y); if(c%gcd!=0) puts("无解"); else { x=x*(c/gcd); printf("%d\n",(x%b+b)%b); } } 4.Lucas求c（n,m）%p （n>10e6用） Lucas(n,m,p)=C(n%p,m%p)* Lucas(n/p,m/p,p) #include<iostream> #include<cstdio> #include<algorithm> #define LL long long using namespace std; int t; LL pow(LL a,LL b,LL p) { LL ans=1; while(b) { if(b&1) ans=(ans*a)%p; a=(a*a)%p; b=b>>1; } return ans; } LL C(LL n, LL m,LL p) { LL i; if(m==0) return 1; if(m>n-m) m=n-m; LL up=1,down=1; for(i=1; i<=m; i++) { up=(up*(n-i+1))%p; down=(down*i)%p; } return up*pow(down,p-2,p)%p; } LL lucas(LL n,LL m,LL p) { if(m==0) return 1; return C(n%p,m%p,p)*lucas(n/p,m/p,p); } int main() { scanf("%d",&t); LL m,n,p; while(t--) { scanf("%lld%lld%lld",&n,&m,&p); printf("%lld\n",lucas(n,m,p)); } return 0; }5.筛选欧拉函数 参考：http://blog.csdn.net/sentimental_dog/article/details/52002608 void init() { euler[1]=1; for(int i=2; i<Max; i++) euler[i]=i; for(int i=2; i<Max; i++) if(euler[i]==i) for(int j=i; j<Max; j+=i) euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出 }
