搜档网
当前位置：搜档网 › ACM常用模板 最大公约数欧拉函数
ACM常用模板 最大公约数欧拉函数
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;
}
相关主题