题目
题目大意
有一道比赛题目, 输入两个整数(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
", (phi[n] << 1) + 1);
}
return 0;
}