Algorithm - Problem - 仪仗队

[SDOI2008] 仪仗队 洛谷 P2158

问题描述

作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 NNN * N 的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。

现在,C君希望你告诉他队伍整齐时能看到的学生人数。

输入

共一个数 NN,(1N400001\leqslant N\leqslant 40000)

输出

共一个数,即C君应看到的学生人数

样例输入
1
4
样例输出
1
9

数论相关

分析

设C君所在的坐标为 (0,0)(0,0),则从C君指向某个人的向量都可以写成 (x,y)(x,y) 的形式 (0x,yN10\leqslant x,y\leqslant N - 1).
现在考虑重复的情况,显然每一个向量 (x,y)(x,y) 都有其最简形式,即存在整数 kk 和向量 (x,y)(x', y') 使得 x=kx,y=ky,gcd(x,y)=1x=kx', y=ky', \gcd(x',y') = 1.
很显然,这样的 (x,y)=(xgcd(x,y),ygcd(x,y))(x',y')=(\frac{x}{\gcd(x,y)}, \frac{y}{\gcd(x,y)}),则计算所有向量的最简形式,看最简形式是否已经计算过,再计数是一种理论可行的方案.
但是这样做实在是太慢了.

N=1N = 1 时,特判为 00.
N>1N > 1 时,不妨从本源出发,要统计的实际上只有最简形式 (x,y)(x', y') 的个数,而 (x,y)(x', y') 满足 gcd(x,y)=1\gcd(x', y') = 1.
x=yx' = y' 时,只有 (1,1)(1, 1) 这一种情况.
x=0x' = 0 时,只有 (0,1)(0, 1) 这一种情况.
y=0y' = 0 时,只有 (1,0)(1, 0) 这一种情况.
假设 2x<yN12\leqslant x' < y' \leqslant N - 1,则此时 (x,y)(x', y') 的个数有 i=2n1φ(i)\displaystyle\sum_{i = 2}^{n - 1}\varphi(i) 个,其中 φ(x)\varphi(x) 是欧拉函数.
根据对称性,2y<xN12\leqslant y' < x' \leqslant N - 1 时个数也有 i=2n1φ(i)\displaystyle\sum_{i = 2}^{n - 1}\varphi(i) 个.
综上,N>1N > 1 时个数有 3+2i=2n1φ(i)\displaystyle 3+2\sum_{i = 2}^{n - 1}\varphi(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
29
30
31
32
#include <iostream>
#include <cstring>
#define MAXN (40000+5)

int phi[MAXN];
void phi_table(int n)
{
memset(phi, 0, sizeof(phi));
phi[1] = 1;
for(int i = 2; i <= n; i++)
{
if(!phi[i])
for(int j = i; j <= n; j = j + i)
{
if(!phi[j]) phi[j] = j;
phi[j] = phi[j] * (i - 1) / i;
}
}
}

int main()
{
int N;
int cnt = 3;
std::cin >> N;
phi_table(N);
for(int i = 2; i <= N - 1; i++)
{
cnt += 2 * phi[i];
}
std::cout << ((N == 1 || N == 0) ? 0 : cnt) << std::endl;
}