【可见的点——欧拉函数】

在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（不包括1）

题目

思路

• 有三个点比较特殊（因为一来这三个点一定可见，同时也无法用gcd == 1判断）：（0，1）、（1，0）、（1，1）
• 对于其他点，我们发现只要 $gcd(x,y)==1$，那就可见，有一类特例就是$x==y$（但是也无妨，因为欧拉函数不算1，算自身，我们可以看作不算自身，算1）
• 我们对称地考虑，考虑 $x>y$的情况，枚举 $x$，计算欧拉函数的值，累加，最后乘2，注意加上上面的三个特例
• 如何计算欧拉函数呢？
  • 做法一：就是利用质因数分解，这个比较麻烦，每次使用都要调用计算
  • 做法二：在欧拉筛的过程中，进行计算，分为四类处理
    • 处理 $\phi (1)=1$
    • 处理 $\phi (p)=p-1,pisaprime$
    • 处理 $\phi (z\ast p)=\phi (z)\cdot p,z\mathrm{mod}p==0$
      • $\phi (z\ast p)$ 起手的 $n$ 比 $\phi (z)$多了 p
    • 处理 $\phi (z\ast p)=\phi (z)\cdot (p-1),z\mathrm{mod}p\ne 0$
      • $\phi (z\ast p)$ 起手的 $n$ 比 $\phi (z)$多了 p，同时还要考虑一个新的质因数 $p$

代码

质因数分解版

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int get_phi(int n)
{int ans = n;for(int i = 2; i*i <= n; i++){if(n % i == 0){ans = ans * (i-1) / i;while(n % i == 0) n /= i;}}if(n > 1) ans = ans * (n-1) / n;return ans;
}int main()
{int t;cin >> t;int cnt = 0;while(t--){int n;cin >> n;int res = 3;for(int x = 2; x <= n; x++){res += 2*get_phi(x);}cout << ++cnt << ' ' << n << ' ' << res << '\n';}return 0;
}

欧拉筛版

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int primes[N], idx;
bool st[N];
int phi[N];
void get_primes(int n)
{phi[1] = 1;for(int i = 2; i <= n; i++){if(!st[i]){primes[++idx] = i;phi[i] = i-1;}for(int j = 1; primes[j]*i <= n; j++){st[primes[j]*i] = true;if(i % primes[j] == 0){phi[primes[j]*i] = phi[i] * primes[j];break;}phi[primes[j]*i] = phi[i] * (primes[j] - 1);}}
}
int main()
{get_primes(1000);int t;cin >> t;int cnt = 0;while(t--){int n;cin >> n;int res = 3;for(int x = 2; x <= n; x++){res += 2*phi[x];}cout << ++cnt << ' ' << n << ' ' << res << '\n';}return 0;
}