求解与n（1-n-1）互质的质因子的个数
补充欧拉函数的知识：（转载）
( 1 ) pk 的欧拉函数
对于给定的一个素数 p ， φ(p) = p -1。则对于正整数 n = pk
φ(n) = pk - pk -1
( 2 ) p * q 的欧拉函数
假设 p, q是两个互质的正整数，则 p * q 的欧拉函数为
φ(p * q) = φ(p) * φ(q) ， gcd(p, q) = 1 。
( 3 ) 任意正整数的欧拉函数
任意一个整数 n 都可以表示为其素因子的乘积为：
I
n = ∏ piki (I 为 n 的素因子的个数)
i=1
根据前面两个结论，很容易得出它的欧拉函数为：
I I
Φ(n) = ∏ piki -1(pi -1) = n ∏ (1 - 1 / pi)
i=1 i=1
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
int eular(int n)
{
int ret=1,i;
for (i=2; i<=sqrt(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;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int temp;
scanf("%d",&temp);
printf("%d\n",eular(temp));
}
return 0;
}