题目链接

题解

首先, 这N+1 * N+1个点, 起点是定为0 还是设置为1呢?

假如是从1开始, 则点(2, 4) 是不被挡的点 (记作A点); 而点(3, 5) (记作B点) 会被 点2, 3挡住.
而假如是从0开始的, 则A点坐标是: (1, 3) 不被挡. B点坐标是(2, 4) 被(1, 2)挡住.

观察来看, 如果是从0开始的, 则一个点(x, y) 被 另一个点(a, b)挡住, 就意味着: 存在c > 1, c | x, c | y, x / c = a, y / c = b
换言之, 如果一个点(x, y) 不被挡, 则不存在这样的c, 也就是: x, y互质.

而这个性质, 在(原点以1开始)的坐标系里, 是不存在的.

也可以这样思考, 在(原点以0开始)的坐标系里, 一个点2, 4, 就意味着: 从原点往左走了2步, 往上走了4步.
那么, 其会被(1, 2)所挡住. 也就是, (a, b)表示: 移动的步数, 也就是 边数

不被挡的点, 除了(0, 0) (0, 1) (1, 0) 这几点涉及到0, 而0不是正数, 在数论问题里 一般要特判处理.
除了(1, 1), 他是对角线点.
那么, 除了这几个点, 其他的点(a, b): (1, a,b >= 1的) (2, 都是对称的, 如果(a,b)不被挡, 则(b,a)也不被挡.)

对于某个固定的l, 有多少个点 (x, l)不被挡, 而且x <= l, 且(x, l)互质, 这就是欧拉函数.

代码

int N;
scanf("%d", &N);
int ans = 3;
FOR_( i, 2, N, 1){
    ans += Euler_phi[ i] * 2;
}
printf("%d %d %d\n", _test_id + 1, N, ans);
1
2
3
4
5
6
7