ovo，这题我一开始竟然没看出来怎么做……
我们不妨设a>b，那么对于每一个a，所能被看到的点的个数就是phi（a），直接求一下欧拉函数的前缀和就行。之后在对于b>a的时候是同理的，还要×2.最后我们发现（1,1）被算了两次，然后还有（0,1）和（1,0）没算，那就再+1.
欧拉函数要线性筛。至于欧拉函数为什么是积性的……这个证明很复杂，反正书上的那个我根本看不懂。有两条重要的性质，第一个是如果一个数i为质数，那么phi（i）=i-1，这个很显然。对于两个互质的数，其乘积的欧拉函数等于二者欧拉函数的乘积，否则若不互质的话（在线性筛的时候也就是对于一个素数和它的倍数），二者乘积的欧拉函数等于那个非素数的欧拉函数×这个素数。（其实不是素数也是成立的）
之后我们就可以在线性筛的时候求出欧拉函数了。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<vector> #include<queue> #define pb push_back #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 40005; const int N = 2000005; const int INF = 1000000009; const ll mod = 51123987; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int pri[M],n,c,tot; ll phi[M]; bool np[M]; void euler() { np[1] = 1,phi[1] = 1; rep(i,2,1500) { if(!np[i]) pri[++tot] = i,phi[i] = i-1; for(int j = 1;i * pri[j] <= 1500;j++) { np[i * pri[j]] = 1; if(!(i % pri[j])) { phi[i*pri[j]] = phi[i] * pri[j]; break; } else phi[i*pri[j]] = phi[i] * (pri[j]-1); } } rep(i,1,1500) phi[i] += phi[i-1]; } int main() { euler(); c = read(); rep(i,1,c) { n = read(); printf("%d %d ",i,n); printf("%lld ",(phi[n] << 1) + 1); } return 0; }