4.1 阶乘最后非 0 位

//求阶乘最后非零位,复杂度 O(nlogn)//返回该位,n 以字符串方式传入#include 
     
      #define MAXN 10000int lastdigit(char* buf){const int mod[20]={
   1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};int len=strlen(buf),a[MAXN],i,c,ret=1;if (len==1)return mod[buf[0]-'0'];for (i=0;i
      
       =0;i--)67c=c*10+a[i],a[i]=c/5,c%=5;}return ret+ret%2*5;}
      
     

4.2 模线性方程组

#ifdef WIN32typedef __int64 i64;#elsetypedef long long i64;#endif//扩展 Euclid 求解 gcd(a,b)=ax+byint ext_gcd(int a,int b,int& x,int& y){int t,ret;if (!b){x=1,y=0;return a;}ret=ext_gcd(b,a%b,x,y);t=x,x=y,y=t-a/b*y;return ret;}//计算 m^a, O(loga), 本身没什么用, 注意这个按位处理的方法 :-Pint exponent(int m,int a){int ret=1;for (;a;a>>=1,m*=m)if (a&1)ret*=m;return ret;}//计算幂取模 a^b mod n, O(logb)int modular_exponent(int a,int b,int n){ //a^b mod nint ret=1;for (;b;b>>=1,a=(int)((i64)a)*a%n)if (b&1)ret=(int)((i64)ret)*a%n;return ret;}//求解模线性方程 ax=b (mod n)//返回解的个数,解保存在 sol[]中68//要求 n>0,解的范围 0..n-1int modular_linear(int a,int b,int n,int* sol){int d,e,x,y,i;d=ext_gcd(a,n,x,y);if (b%d)return 0;e=(x*(b/d)%n+n)%n;for (i=0;i
     
      0,w[i]与 w[j]互质,解的范围 1..n,n=w[0]*w[1]*...*w[k-1]int modular_linear_system(int b[],int w[],int k){int d,x,y,a=0,m,n=1,i;for (i=0;i
     

4.3 素数

//用素数表判定素数,先调用 initprimeint plist[10000],pcount=0;int prime(int n){int i;if ((n!=2&&!(n%2))||(n!=3&&!(n%3))||(n!=5&&!(n%5))||(n!=7&&!(n%7)))return 0;for (i=0;plist[i]*plist[i]<=n;i++)if (!(n%plist[i]))return 0;return n>1;}69void initprime(){int i;for (plist[pcount++]=2,i=3;i<50000;i++)if (prime(i))plist[pcount++]=i;}//miller rabin//判断自然数 n 是否为素数//time 越高失败概率越低,一般取 10 到 50#include 
     
      #ifdef WIN32typedef __int64 i64;#elsetypedef long long i64;#endifint modular_exponent(int a,int b,int n){ //a^b mod nint ret;for (;b;b>>=1,a=(int)((i64)a)*a%n)if (b&1)ret=(int)((i64)ret)*a%n;return ret;}// Carmicheal number: 561,41041,825265,321197185int miller_rabin(int n,int time=10){if (n==1||(n!=2&&!(n%2))||(n!=3&&!(n%3))||(n!=5&&!(n%5))||(n!=7&&!(n%7)))return 0;while (time--)if(modular_exponent(((rand()&0x7fff<<16)+rand()&0x7fff+rand()&0x7fff)%(n-1)+1,n-1,n)!=1)return 0;return 1;}
     

4.4 欧拉函数

int gcd(int a,int b){return b?gcd(b,a%b):a;}inline int lcm(int a,int b){
    return a/gcd(a,b)*b;}//求 1..n-1 中与 n 互质的数的个数int eular(int n){int ret=1,i;for (i=2;i*i<=n;i++)if (n%i==0){n/=i,ret*=i-1;while (n%i==0)n/=i,ret*=i;}if (n>1)ret*=n-1;return ret;}