Problem Statement
给定正整数 $n$，求 $1\le x,y\le n$ 且 $\gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对。
只有一行一个整数，代表$n$。
Output
一行一个整数表示答案。
Sample Output
Explanation of example
对于样例，满足条件的 $(x,y)$ 为 $(2,2)$，$(2,4)$，$(3,3)$，$(4,2)$。
Constraints
- 对于 $100%$ 的数据，保证 $1\le n\le10^7$。
Solving
本题实际上是一个对欧拉函数性质的考察：
$$
\sum_{d\in prime}\sum_{i=1}^n\sum_{j=1}^n\left[\text{gcd(i,j)==d} \right]
$$
而在欧拉函数的性质中，有以下两个常用推论：
推论 #1
欧拉函数的第n项前缀和等于满足gcd(i,j)==1的数对(i,j)的数量,1 <= i,j <= n;
推论 #2
要求满足gcd(i,j) = d的数对(i,j)的数量时,可以令 i = d * a,j = d * b,将问题转化为求满足gcd(a,b) = 1 的数对(a,b)的数量,其中 1 <= a,b <= n/d.
再利用推轮#1我们可以得出:
$$
cnt = \sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\phi(i)
$$
要注意:
数对(i,j)不表示全部数对,若要求全部数对则要求 数对(i,j) + 数对(j,i) - (i==j的情况=1)
即要求出题目的答案,应该是要求 cnt * 2 - 1
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
71
|
#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 = 1e7+10;
const int M = 0;
vector<int> prime;
bitset<N> not_prime;
ll prefix[N];
int phi[N];
int cnt = 0;
void Euler_phi(int n)
{
phi[1] = 1;
for(int i=2;i<=n;i++)
{
if(!not_prime[i])
{
prime.push_back(i);
cnt++;
phi[i] = i - 1;
}
for(int pri_j : prime)
{
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;
prefix[1] = phi[1];
Euler_phi(n);
ll ans = 0;
for(int i=1;i<=n;i++) prefix[i] = prefix[i-1] + phi[i];
for(int i=0;i<cnt;i++)
{
ans += prefix[n/prime[i]]*2-1;
}
cout << ans;
}
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;
}
|