宣传一下 算法提高课整理

CSDN个人主页：更好的阅读体验

原题链接

题目描述

给定整数 $N$，求 $1 \le x,y \le N$ 且 $\gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对。

输入格式

输入一个整数 $N$。

输出格式

输出一个整数，表示满足条件的数对数量。

数据范围

$1 \le N \le 10^7$

输入样例：

4

输出样例：

4

思路

首先考虑暴力。

本题答案为：
$$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{p \in \mathbb{P}}^{}[\gcd(i,j)=p]$$

把 $\gcd(i,j)=p$ 变成 $\gcd(i,j)=1$ 然后把 $p$ 除到前面的 $n$ 里。

即：$$\sum_{p \in \mathbb{P}}^{}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}[\gcd(i,j)=1]$$

和 5.5.1 可见的点 相同，我们可以将以上代数式变换为：

$$2 \times\sum_{p \in \mathbb{P}}^{}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i)+1$$

这里不再进行推导，读者可以自行点击上方链接进行阅读。

此时进行计算，时间复杂度近似为 $\large{O(\frac{n^2}{\ln n})}$，将 $n=10^7$ 代入计算，发现超过 $10^8$，在 $1s$ 的时限内会 $\text{TLE}$。

我们看到 $\large\sum_{i=1}^{\frac{n}{p}}\varphi(\frac{n}{p})$ 可以考虑预处理欧拉函数前缀和。

假设 $\large{s_k=\sum_{i=1}^{k}\varphi(i)}$，则原式可化为：

$$\large{2 \times\sum_{p \in \mathbb{P}}^{}s_{\lfloor\frac{n}{p}\rfloor}+1}$$

此时我们枚举 $n$ 的所有质因数进行计算就不会超时。

算法时间复杂度

预处理 $\varphi(i)$：$O(n)$;
预处理 $s_i$：$O(n)$;
计算结果：$\large{O(\frac{n}{\ln n})}$。

因此最高时间复杂度：$O(n)$，可以过。

注意： 数论题目中，开 long long 已经是常识，所以很有必要写一条 #define int long long 避免犯错。

AC Code

$\text{C}++$

#include <iostream>
#define int long long

using namespace std;

const int N = 1e7 + 10;

int n;
int primes[N], cnt;
int euler[N], s[N];
bool st[N];

void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

main()
{
    scanf("%lld", &n);
    get_eulers(n); // 线性筛质数和欧拉函数

    for (int i = 1; i <= n; i ++ ) // 预处理欧拉函数前缀和
        s[i] = s[i - 1] + euler[i];

    int res = 0;
    for (int i = 0; i < cnt; i ++ ) // 枚举 n 以内的质数
        res += 2 * s[n / primes[i]] - 1;

    printf("%lld\n", res);
    return 0;
}

最后，如果觉得对您有帮助的话，点个赞再走吧！