UVa 10820 Send a Table (欧拉函数)

发表于 更新于 分类于

题目

题目大意

有一道比赛题目, 输入两个整数\(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)\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}