题目
题目大意
有一道比赛题目, 输入两个整数\(x\)、\(y\)(\(1 ≤ x, y ≤ n\)), 输出某个函数\(f(x, y)\)。有位选手想交表(即事先计算出所有的\(f(x, y)\), 写在源代码里), 但是表太大了, 源代码超过了比赛的限制, 需要精简。
好在那一道题目有一个性质, 使得很容易根据\(f(x, y)\)算出\(f(xk, yk)\)(其中\(k\)是任意正整数), 这样有一些\(f(x, y)\)就不需要存在表里了。
输入\(n\)(\(n ≤ 50000\)), 你的任务是统计最简的表里有多少个元素。例如, \(n = 2\)时有\(3\)个: \((1, 1)\), \((1, 2)\), \((2, 1)\)。
题解
显然题目的本质是: 输入\(n\), 有多少个二元组\((x, y)\)满足\(1 ≤ x, y ≤ n\)且\(x\)、\(y\)互质。若\(x\)、\(y\)不互质, 则\((x, y) > 1\), 设\((x, y) = k\)、\(ak = x\)、\(bk = y\), 显然可以通过\(f(a, b)\)计算得到\(f(x, y)\)。
不难发现除\((1, 1)\)外, 其他满足条件的二元组都满足\(x ≠ y\)。设\(x < y\)的二元组有\(F(n)\)个, 那么答案就是\(2F(n) + 1\)。
对照欧拉函数定义, 可得\(F(n) = \Sigma_{i = 2}^n \phi(i)\)
代码
#include <cstdio>
long long phi[50010], prime[50010], total;
bool mark[50010];
int n;
int main(int argc, char const *argv[]) {
phi[1] = 1;
for (register long long i(2); i <= 50000; ++i) {
if (!mark[i]) {
prime[++total] = i,
phi[i] = i - 1;
}
for (register long long j(1); j <= total && i * prime[j] <= 50000; ++j) {
mark[i * prime[j]] = 1;
if (!(i % prime[j])) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
} else {
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
for (register int i(3); i <= 50000; ++i) phi[i] += phi[i - 1];
phi[1] = 0;
while (~scanf("%d", &n) && n) {
printf("%lld\n", (phi[n] << 1) + 1);
}
return 0;
}