算法1
(欧拉函数) $O(n)$
本题要求的是 $x, y <= n$ 时 $gcd(x, y)$ 为质数的方案数。
因为 $gcd$ 的结果不唯一,所以我们要进行化简。
设 $p$ 为一个质数,则满足 $gcd(x, y) = p$ 时,有 $gcd( \frac{x}{p} , \frac{y}{p} ) = 1$
由此将问题转化为解决 $gcd(x, y) = 1$ 的方案数,也就是 $x$ 和 $y$ 互质的方案数。
将 $x$ 与 $y$ 之间的关系分成两类 $x > y$ 和 $x < y$。
对于其中任意一类,都可以转化为求出 $1$ 到 $n$ 中每个数的欧拉函数,
也就是当确定 $x$ 的值时,计算 $y$ 有多少种不同情况,令 $x$ 和 $y$ 互质。
值得注意的是,$x = y$ 时,也为互质,这要进行特判。
用数组 $s$,统计前缀和 $s[i] = s[i - 1] + * phi[i]$
记得将预处理的数组转化为实际答案。
枚举质数 $p_i$,将答案累计,注意其上界为 $n / p_i$ 下取整。
$res += 2 * s[n / p_i] + 1$
时间复杂度
线性筛时间复杂度为 $O(n)$
C++ 代码 (需要开 $long long$)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
int n, m;
long long phi[N], p[N], v[N], s[N];
long long res;
inline bool check(int a, int b) // a % b 的常数优化
{
return a / b * b == a;
}
void init(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!v[i])
{
p[ ++ m] = i;
phi[i] = i - 1;
}
for (int j = 1; p[j] <= n / i; j ++ )
{
v[i * p[j]] = 1;
if (check(i, p[j]))
{
phi[i * p[j]] = phi[i] * p[j];
break;
}
phi[i * p[j]] = phi[i] * (p[j] - 1);
}
}
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + phi[i]; // 前缀和
for (int i = 1; i <= m; i ++ ) res = res + s[n / p[i]] * 2 + 1; // 两种情况加特殊
}
int main()
{
scanf("%d", &n);
init(n);
printf("%lld", res);
}
兄弟互一下粉