话不多说，直接粘模板
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
此乃欧几里得算法，就是小学的辗转相除法
int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
欧拉函数，求对正整数n，小于n的数中与n互质的数的数目。找到这个数的所有因子，将把(1- 1/p)转换为，(p - 1) / p，筛去相同的因子。欧拉函数式子Φ（n）= n * (1-1/p1) * (1-1/p2) * …(1-1/pk)。
不想粘了，出了点事情，为什么我的学习之路充满坎坷。😂