欧拉函数 get ！

· · 个人记录

欧拉函数，也叫 φ 函数，作用是求小于某个数并与它互质的数的个数

证明就不写了，什么中国剩余定理什么的真让人头大

欧拉函数有两个性质：

  1. φ$ 函数是积性函数，即 $φ ( m \times n ) = φ ( m ) \times φ ( n )

  2. 如果 n 为奇数，φ ( 2n ) = φ ( n )

模板：

//线性筛欧拉函数 
int vis[MAXN],phi[MAXN],prime[MAXN];
int tot;//vis 为确定是否是素数，tot是素数个数

void Euler_Phi()
{
    phi[1] = 1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            phi[i]  = i-1;
            prime[++tot] = i;
        }
        for(int j=1;j<=tot && prime[j]*i<=n;j++)
        {
            int mul = i*prime[j];
            vis[mul] = 1;
            if(i%prime[j] == 0)
            {
                phi[mul] = phi[i]*prime[j];
                break;    
            }
            else
                phi[mul] = phi[i]*(prime[j]-1);
        }
    }
}

//单个数的欧拉函数 
int euler_Phi(int n)
{
    int m = (int)sqrt(n+0.5);
    int ans = n;
    for(int i=2;i<=m;i++)
        if(n%i == 0)
        {
            ans = ans/i*(i-1); //先做除法，防止爆 int 
            while(n%i == 0) n /= i;
        }
    if(n > 1)   ans = ans/n*(n-1);
    return ans;
}

试炼：

传送门

由题意可以发现，只有斜率不同时，才能连线

所以对于一个点 ( x , y ) ，如果

gcd ( x , y ) = 1

那么就可以连线，所以要找的就是互质的两个数

就可以使用欧拉函数了

可以先算上半个三角形的答案，再乘 2 加 3 （垂直的两个和对角线上的一个）

这样就可以用线性筛欧拉函数了

int m[MAXN],phi[MAXN],prime[MAXN];
// m 为小于 i 的最小质数

void Euler_Phi()
{
    m[1] = 1;
    for(int i=2;i<n;i++)
    {
        if(!m[i])
        {
            prime[++tot] = i;
            phi[i] = i-1;
            m[i] = i;
        }
        for(int j=1;j<=tot && prime[j]*i<=n;j++)
        {
            int k = prime[j]*i;
            m[k] = prime[j];
            if(m[i] == prime[j])
                    phi[k] = phi[i]* prime[j];
            else    phi[k] = phi[i]*(prime[j]-1);
                    //运用了函数的积性
        }
    }
}

int main(void)
{
    cin >> n;
    if(n == 1)
    {
        cout << "0";
        return 0;
    }
    Euler_Phi();
    for(int i=1;i<n;i++)    ans += phi[i];
    cout << ans*2+3;
    return 0;
}