Aimee

很显然，对于每一行来讲，如果他们$gcd(x,y)$不为1，那么这个斜率一定出现过，所以说呢，需要排除

再结合一下对称性，可以知道对于每一列，可用的点对就是$psi(x)$

最后的答案就是$3+2*sum_{i=2}^{n-1}psi(i)$

为什么是n-1呢，因为体委再(1,1)处

那么问题来了，怎么求欧拉函数

欧拉函数

首先我们有$psi(n)=n*prod_{prime quad p|n}(1-frac{1}{p})$

这个东西是怎么来的呢，考虑一下算数基本定理，对于任意两个质因数p,q，在1~n中分别有$frac{n}{p}$ $frac{n}{q}$

个他们的倍数，减去他们，但是也要去掉多减的pq部分，就会有
$$
n-frac{n}{p}-frac{n}{q}+frac{n}{pq}=n(1-frac{n}{p})(frac{n}{q})
$$
这样就可以计算了，这是个积性函数

积性函数

$$
f(ab)=f(a)(b)quad gcd(a,b)=1
$$

欧拉函数的一些性质

对于指数p 若$p|n & p^2|n$那么有$psi(n)=psi(n/p)*p$

对于指数p 若$p|n & n%p^2neq0$那么有$psi(n)=psi(n/p)*p$

不使用这些性质，可以搞出改造后的埃氏筛 $O(nlog n)$做法

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int phi[400001];
int znx;
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;++i) phi[i]=i;
    for(int i=2;i<=n;++i){
        if(phi[i]==i){
            for(int j=i;j<=n;j+=i){
                phi[j]=phi[j]/i*(i-1);
            } 
        }
        if(i!=n)
        znx+=phi[i]+phi[i]; 
    } 
    if(n==1){
        cout<<0;
    }else
    cout<<znx+3;
    return 0;
}

但是完全可以搞成线性的，利用上面提到的性质，改造欧拉筛

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int phi[400001];
int znx;
int prime[400001];
int p;
int v[400001];
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;++i) phi[i]=i;
    for(int i=2;i<=n;++i){
        if(v[i]==0){
            v[i]=i;
            prime[++p]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=p;++j){
            if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
        }
        if(i!=n)
        znx+=phi[i]+phi[i]; 
    } 
    if(n==1){
        cout<<0;
    }else
    cout<<znx+3;
    return 0;
}

和平常的似乎不太一样啊
break呢？
没错，它慢了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int phi[400001];
int znx;
int prime[400001];
int p;
int v[400001];
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;++i) phi[i]=i;
    for(int i=2;i<=n;++i){
        if(v[i]==0){
            v[i]=i;
            prime[++p]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=p;++j){
            if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
            if(i%prime[i]==0)
            break;
        }
        if(i!=n)
        znx+=phi[i]+phi[i]; 
    } 
    if(n==1){
        cout<<0;
    }else
    cout<<znx+3;
    return 0;
}