最大公约数欧拉函数.txt

数论的基础有素数删选质因数的分解公约数的求解等

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;
}