目录

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

互质与欧拉函数

1. 算法分析

基本概念
欧拉函数：1~N中与N互质的数的个数
在算术基本定理中:N = (p1a1) * (p2a2) * ... *(pmam)
一个数的欧拉函数: φ(N)=N * (1-1/p1) * (1-1/p2) * ... * (1-1/pm)
且φ(1) = φ(2) = 1

重要结论
1~N中，(x, y) = 1的对数为: 前1~N的欧拉函数的前缀和 * 2 - 1

常用思路
很多求gcd(x, y)=p的问题，最后都需要转化为(x/p, y/p)=1,然后变为求互质的数目，转化为欧拉函数求解

2. 板子

  1. 求N的欧拉函数 O(sqrt(N))
int get_euler(int a)
{
    long long res = a;  // 存储答案
    for (int i = 2; i <= a / i ;++i)  // 求出小于等于sqrt(a)的质数
    {
        if (a % i == 0)
        {
            res = res * (i - 1) / i;  // 欧拉函数公式求答案
            while (a % i == 0) a /= i;
        }
    }
    if (a > 1) res = res * (a - 1) / a;
    return res;
}
  1. 求1~N的欧拉函数和 O(N)
phi[1] = 1;
long long res = 0;
for (int i = 2; i <= n; ++i )  // 求质数
{
    if (!st[i])   // 没记录就标记这个质数
    {
        prime[cnt++] = i;
        phi[i] = i - 1;  // 质数的欧拉函数为本身减一
    }
    for (int j = 0; prime[j] <= n / i; ++j)  // 枚举所有的质数
    {
        st[prime[j] * i] = 1;
        if (i % prime[j] == 0 ) // 如果i能够整除pj
        {
            phi[i * prime[j]] = prime[j] * phi[i];  // phi(i * pj) = pj * phi[i]
            break;
        }
        phi[i * prime[j]] = phi[i] * (prime[j] - 1);  // phis(i * pj) = phi(i) * (pj - 1)
    }
}
for (int i = 1; i <= n; ++i) res += phi[i];  // 累加每个数的欧拉函数

3. 例题

acwing201 可见的点
在一个平面直角坐标系的第一象限内，如果一个点(x,y)与原点（0,0）的连线中没有通过其他任何点，则称该点在原点处是可见的。
1000组测试样例, 每组测试样例1000个数
互质与欧拉函数 算法 第1张

/*
如果(x, y)是互质的，那么说明x和y是最小的单位，不可以往后投影，也就是不能挡住其他点
所以只需要判断当前的x上，有多少y和这个x互质
那么欧拉函数
求前n个点就是求前1~N的欧拉函数和
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
int const N = 1e3 + 10;
int phi[N], prime[N], cnt, st[N], n, c;

int main() {
    cin >> c;
    for (int k = 1; k <= c; ++k) {
        memset(st, 0, sizeof st);
        memset(phi, 0, sizeof phi);
        memset(prime, 0, sizeof prime);
        cnt = 0;
        cin >> n;
        phi[1] = 1;
        LL res = 0;
        for (int i = 2; i <= n; ++i )  // 求质数
        {
            if (!st[i])   // 没记录就标记这个质数
            {
                prime[cnt++] = i;
                phi[i] = i - 1;  // 质数的欧拉函数为本身减一
            }
            for (int j = 0; prime[j] <= n / i; ++j)  // 枚举所有的质数
            {
                st[prime[j] * i] = 1;
                if (i % prime[j] == 0 ) // 如果i能够整除pj
                {
                    phi[i * prime[j]] = prime[j] * phi[i];  // phi(i * pj) = pj * phi[i]
                    break;
                }
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);  // phis(i * pj) = phi(i) * (pj - 1)
            }
        }
        for (int i = 1; i <= n; ++i) res += phi[i];  // 累加每个数的欧拉函数
        cout << k << " " << n << " " << res * 2 + 1 << endl;
    }
}

acwing220最大公约数
给定整数N，求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。
N~1e7
互质与欧拉函数 算法 第2张

/*
本题求1~N中的(x, y),使得(x, y)=p(p为质数)
可以把p除以到x和y中，得到(x/p,y/p)=1
那么就是求[1, N/p]中，找出(t1, t2)=1
通过画图可以转化为acwing201可见的点那题
但本题和那题不一样的区别在于那题是求[0,N]内(x, y)的对数，答案为1~N的欧拉函数的前缀和*2+1
而本题通过画图可以知道，是求2~N的欧拉函数的前缀和*2 + 1
那么只要把phi[1]=0,然后求1~N的欧拉函数的前缀和即可
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
int const N = 1e7 + 10;
int prime[N], cnt, st[N], n, phi[N];
LL sum[N];

// 求1~N的欧拉函数的前缀和
void init(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i )  // 求质数
    {
        if (!st[i])   // 没记录就标记这个质数
        {
            prime[cnt++] = i;
            phi[i] = i - 1;  // 质数的欧拉函数为本身减一
        }
        for (int j = 0; prime[j] <= n / i; ++j)  // 枚举所有的质数
        {
            st[prime[j] * i] = 1;
            if (i % prime[j] == 0 ) // 如果i能够整除pj
            {
                phi[i * prime[j]] = prime[j] * phi[i];  // phi(i * pj) = pj * phi[i]
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);  // phis(i * pj) = phi(i) * (pj - 1)
        }
    }
    phi[1] = 0;
    for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + 0ll + phi[i];
}

int main() {
    cin >> n;
    init(n);
    LL res = 0;
    for (int i = 0; i < cnt; ++i) {
        LL tmp = 1;
        int p = prime[i];
        tmp += (LL)sum[n / p] * 2;
        res += tmp;
    }
    cout << res;
    return 0;
}

acwing221龙哥的问题
求出∑1≤i≤Ngcd（i，N)的值。
N~1e9
互质与欧拉函数 算法 第3张

#include <bits/stdc++.h>

using namespace std;

int const N = 1e5 + 10;

typedef long long LL;
int n;

LL get_euler(LL a)
{
    LL res = a;  // 存储答案
    for (int i = 2; i <= a / i ;++i)  // 求出小于等于sqrt(a)的质数
    {
        if (a % i == 0)
        {
            res = res * (i - 1) / i;  // 欧拉函数公式求答案
            while (a % i == 0) a /= i;
        }
    }
    if (a > 1) res = res * (a - 1) / a;
    return res;
}

int main() {
    cin >> n;
    LL res = 0;
    for (int i = 1; i <= n / i; ++i) {
        if (n % i == 0) {
            res += i * get_euler(n / i);
            if (n/i != i) res += (n / i) * get_euler(i);    
        }
    }
    
    cout << res;
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄