关于数论

int n,phi[N],prime[N],cnt;
bool pri[N];

void Phi(){
	mst(pri,1);
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(pri[i]){
			prime[++cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt;j++){
			int k=i*prime[j];
			if(k>n){
				break;
			}
			pri[k]=0;
			if(i%prime[j]==0){
				phi[k]=prime[j]*phi[i];
				break;
			}else{
				phi[k]=(prime[j]-1)*phi[i];
			}
		}
	}
}

// 递归形式
int gcd(int x, int y) {
    return(y == 0 ? x : gcd(y, x%y));
}

// 非递归形式
int gcd(int x, int y) {
    int r=x%y;
    while(r){
        x=y;
        y=r;
        r=x%y;
    }
    return y;
}

//懒狗形式
__gcd();

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