UVa 10214 Trees in a Wood. (欧拉函数)

发表于 更新于 分类于

题目

题目大意

在满足\(|x| ≤ a\), \(|y| ≤ b\)(\(a ≤ 2000\), \(b ≤ 2000000\))的网格中, 处了原点之外的整点(即\(x\), \(y\)坐标均为整数的点)各种着一棵树。数的半径可以忽略不计, 但是可以相互遮挡。求从原点能看当多少棵树。设这个值为\(K\), 要求输出\(\frac{K}{N}\), 其中\(N\)为网格中树的总数。

题解

显然四个坐标轴上各只能看见一棵树, 所以可以只数第一象限, 答案乘以\(4\)后加\(4\)。第一象限的所有\(x\), \(y\)都是正整数, 能看到\((x, y)\), 当且仅当\((x, y) = 1\)。

由于评测机不是神威·太湖之光\(a\)范围比\(b\)小, 一列一列统计不怕超时, 可以分区间计算: 1. \(1 ≤ y ≤ x\): 有\(\phi(x)\)个, 这是欧拉函数的定义 2. \(x + 1 ≤ y ≤ 2x\): 也有\(\phi(x)\)个, 因为\((x + i, x) = (x, i)\) 3. \(2x + 1 ≤ y ≤ 3x\): 也有\(\phi(x)\)个, 因为\((2x + i, x) = (x, i)\) 4. \(\cdots\)

代码

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 <cstdio>
long long phi[2010];
long long a, b, ans;
long long gcd[2010][2010];
inline long long GreatestCommonDivisor(const long long&, const long long&);
int main(int argc, char **argv) {
  phi[1] = 1;
  for (register int i(2); i <= 2000; ++i) {
    if (!phi[i]) {
      for (register int j(i); j <= 2000; j += i) {
        if (!phi[j]) phi[j] = j;
        phi[j] = phi[j] / i * (i - 1);
      }
    }
  }
  for (register int i(1); i <= 2000; ++i) {
    for (register int j(1); j <= 2000; ++j) {
      gcd[i][j] = GreatestCommonDivisor(i, j);
    }
  }
  while (~scanf("%lld %lld", &a, &b) && (a || b)) {
    ans = 0;
    for (register int i(1); i <= a; ++i) {
      ans += phi[i] * (b / i);
      for (register int j(1); j <= b % i; ++j) {
        ans += gcd[i][j] == 1;
      }
    }
    printf("%.7lf\n", (double((ans << 2) + 4)) / double(((a << 1) | 1) * ((b << 1) | 1) - 1));
  }
  return 0;
}
inline long long GreatestCommonDivisor(const long long &x, const long long &y) {
  return y ? (gcd[x][y] ? gcd[x][y] : GreatestCommonDivisor(y, x % y)) : x;
}