UVA 10820 Send a Table

发表于 | 分类于 ，

所有可能的数对数量为N×N
所求的（x，y）一定满足x，y互素，否则设公约数为t，（x，y）可由（x/t，y/t）得到
若（x，y）互素，那么（y，x）也互素
若能求出满足1<=x<=N，1<=y<=x的互素的（x，y），那么经过对称即可得到所有的数对（可从N×N的二维图上来理解）

求phi值时注意避免溢出

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
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 50000;

int N;
int phi[MAX_N + 1];

void euler_function(int N) {
  for (int i = 1; i <= N; i++) phi[i] = i;
  for (int i = 2; i <= N; i++) {
    // phi[i] == i, then i is prime
    if (phi[i] != i) continue;
    for (int j = i; j <= N; j += i) {
      // first / i then * (i - 1)
      // ensures phi[j] <= j and no overflow
      phi[j] = phi[j] / i * (i - 1);
    }
  }
}

int main() {
  euler_function(MAX_N);

  while (scanf("%d", &N) && N) {
    int res = 0;
    for (int i = 1; i <= N; i++) res += phi[i];
    res = res * 2 - 1;

    printf("%d\n", res);
  }

  return 0;
}