欧拉函数是指对于正整数x，小于或等于x的数中与x互质的数的数量，通常用φ(x)表示。
我们先看一道例题
对题意进行分析，可以得到最小生成树中的两个直接连通的点的gcd一定是1，我们要统计最小生成树的个数，也就是求1~n每个数的欧拉函数值之和。
因此，对于一个正整数x，我们需要计算欧拉函数φ(x)。
1.求单个数的欧拉函数值
我们不妨通过几个简单的值推测一下。
①当x=1是，显然φ(x)=1
②当x为质数时，φ(x)=x-1
③当x可以写成pk的形式时（x,k均为正整数），
这里有必要解释一下，
对于任意正整数x，我们将其分解质因数，如下图所示，得出欧拉函数的计算公式
因此，我们得出了求一个数的欧拉函数值的解法，时间复杂度为O(n√n).
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int n; 5 ll ans; 6 int main() { 7 scanf("%d", &n); 8 ans = n; 9 int maxx = sqrt(n); 10 for (register int i = 2; i <= maxx; ++i) { 11 if (n % i == 0) { 12 ans = ans / i * (i - 1); 13 while (n % i == 0) n /= i; 14 } 15 } 16 if (n > 1) ans = ans / n * (n - 1); 17 printf("%lld\n", ans); 18 return 0; 19 }
2.线性筛求1~n每个数的欧拉函数值
众所周知，我们可以用线性筛在O(n)的时间内求出1~n的质数表。我们将该算法加以改造，便能在O(n)时间内求出任何积性函数的值
原文：https://www.cnblogs.com/shl-blog/p/11084899.html
