int gcd(int a,int b) {
while(b) {
int t=a%b;
a=b;
b=t;
}
return a;
}
int powmod(int a,int n,int m) {
if(n==1)return a%m;
if(n==0)return 1;
int tmp=powmod(a,n>>1,m)%m;
tmp=tmp*tmp%m;
if(n&1)tmp*=a;
tmp%=m;
return tmp;
}
int euler(int x) {
int i, res=x;
for (i = 2; i < (int)sqrt(x * 1.0) + 1; i++)
if(x%i==0) {
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
......
阅读全文