Problem Statement
作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 $N \times N$ 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。
现在，C 君希望你告诉他队伍整齐时能看到的学生人数。
一行，一个正整数 $N$。
Output
输出一行一个数，即 C 君应看到的学生人数。
Sample Output
Constraints
对于 $100 %$ 的数据，$1 \le N \le 40000$。
Solving
我们设C君所占的地方坐标为(0,0),可以得出能被看到的地方(x,y)都满足gcd(x,y)=1
由欧拉函数的性质，我们可以得出：
以(1,1)为顶点，边长为n-1的正方形区域内所能看到的人数为：
$$
ans =2\sum_{x=1}^{n-1}\sum_{y=1}^{n-1}[gcd(x,y)=1]=2\sum_{i=2}^{n-1}\phi(i)
$$
其中phi[1]=1但无意义，为方便理解我们不将其算入其中。
即答案不包括顶点(1,1)和(0,1),(1,0)三个人，此时答案cnt也无需再-1;
如果算入phi[1]=1的情况，则算出ans后还需-1才能准确算出整个正方形区域C君能看到的点(因为(1,1)点会被加两次),此时答案加上(1,0)和(0,1)两个特殊点后将变为ans + 1;
故算出ans+3就是所求答案：
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define NINF -0x3f3f3f3f
#define Single
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 40005;
const int M = 0;
vector<int> pri;
bitset<N> not_prime;
int phi[N];
void Euler_Phi(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!not_prime[i])
{
pri.push_back(i);
phi[i] = i - 1;
}
for (int pri_j : pri)
{
if (i * pri_j > n) break;
not_prime[i * pri_j] = true;
if (i % pri_j == 0)
{
phi[i * pri_j] = phi[i] * pri_j;
break;
}
phi[i * pri_j] = phi[i] * phi[pri_j];//积性函数性质
}
}
}
void solve()
{
int n;
cin >> n;
Euler_Phi(n);
ll ans = 0;
for(int i=2;i<=n-1;i++)
{
ans += phi[i];
}
if(n==1)//注意特殊情况的特判
{
cout << 0;
return;
}
cout << ans * 2 + 3;//加上三个特殊点
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T;
#ifdef Single
T = 1;
#else
cin >> T;
#endif
while(T--)
{
solve();
}
return 0;
}
|