数论的板子

inline int gcd(x,y){
  return (y==0)?x:gcd(y,x%y);  
} 

inline void gcd(int x,int y){
	int i,j;
    if(!x)return y;if(!y)return x;
    for(i=0;!(x&1);i++)x>>=1;
    for(j=0;!(j&1);j++)j>>=1;
    i=min(i,j);
    while(true){
        if(x<y){x^=y;y^=x;x^=y;}
        if(!(x-=y))return y<<i;//这里也可以减法改成模
        while(!(x&1))x>>=1;//消除所有的2
    }
}

int exgcd(int a,int b,int &x,int &y){
    if(!b){x=1;y=0;return a;}
    int gcd=exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-b/a*y;
    return gcd;
}

int inv(int n,int p){
    //这里面求的是n在mod p情况下的逆元
	if(n==1)return 1;
	else return -(p/n)*inv(p%n,p);
}

int prm[maxn],cnt=0;
bool isp[maxn]={1,1};//记录哪一些数不是质数
void Eular_Sieve(){
    for(int i=2;i<maxn;i++){
        if(!isp[i])prm[++cnt]=i;
        for(int j=1;j<cnt and i*prm[j]<maxn;j++){
            isp[i*prm[j]]=true;
            if(!(i%prm[j]))break;
        }
    }
}

int prm[maxn],phi[maxn],cnt=0;
bool isp[maxn]={1,1};//记录哪一些数不是质数
void Eular_Sieve(){
    phi[1]=1;
    for(int i=2;i<maxn;i++){
        if(!isp[i])prm[++cnt]=i,phi[i]=i-1;//质数的phi值等于他自己减去1
        for(int j=1;j<cnt and i*prm[j]<maxn;j++){
            isp[i*prm[j]]=true;
            if(!(i%prm[j])){
			   phi[i*prm[j]]=phi[i]*prm[j]
                break;
            }      
            else phi[i*prm[j]]=phi[i]*(prm[j]-1);
        }
    }
}

int Lucas(int n,int m,int p){
	int res=1,a,b;
    while(n&&m){
    	int a=n%p,b=b%p;
        if(a<b)return 0;
        (res*=C(a,b,p))%=p;
        n/=p;m/=p;
    }
    return res;
}

long long qkpow(long long b,int p,int mod){
	long long res=1;
	while(p){
		if(p&1){
			(res*=b)%=mod;
		}
		(b*=b)%=mod;
		p>>=1;
	}
	return res;
}
long long C(int n,int m,int p){
	if(n<m)return 0;
	if(n==m)return 1;
	if(m>n-m)m=n-m;//约掉 
	long long s1=1,s2=1;
	for(int i=0;i<m;i++){
		s1=s1*(n-i)%p;
		s2=s2*(i+1)%p;
	}
	return s1*qkpow(s2,p-2,p)%p;
}
long long Lucas(int n,int m,int p){
	if(m==0)return 1;
	return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}

f[0]=1
for(int i=1;i<=N;i++){
    for(int j=0;j<i;j++){
        f[i]=f[j]*f[i-1-j];
    }
}

f[0]=1;
for(int i=1;i<=N;i++){
	f[i]=((4*i-2)*f[i-1])/(i+1);
}