【Day 2】反演例题

A - Problem b

链接
题目

对于给出的 n 个询问,每次求有多少个数对 (x,y) ,满足 a ≤ x ≤ b , c ≤ y ≤ d ,且 gcd(x,y) = k , gcd(x,y) 函数为 x 和 y 的最大公约数。

思路:

在这里插入图片描述

关于 F[i] 的计算说明

[1,n] 中 的 i ,2i, 3i, … ,n/i

[1,m] 中的 i, 2i, 3i, … ,m/i

两两满足 gcd(x,y) == i

首先,对

于 $x \in [1,a] $ , $y \in [1,b] $ ,使得 $gcd(x,y) == k$ 的 $(x,y)$ 的对数

等价于

$x \in [1,a/k] $ , $y \in [1,b/k] $ ,使得 $gcd(x,y) == 1$ 的 $(x,y)$ 的对数

而对与区间 $[a,b] [c,d]$ 可以进行*容斥

$[a,b][c,d] == [1,b][1,d] - [1,b][1,c-1] - [1,d][1,a-1] + [1,a-1]*[1,c-1] $

用 $f(a,b)$ 来表示

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
/*
给定 a,b c,d , k
求 [a,b] 中的x 和 [c,d] 中的y
满足 gcd(x,y) == k
的对数
*/

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;
int mu[maxn];
int sum[maxn];
int vis[maxn];
int prime[maxn];
int cnt;

void get_mu(int n){ //线性筛
mu[1] = 1;
for(int i = 2;i <= n;i++){
if(!vis[i]){
prime[++cnt] = i;
mu[i] = -1;
}
for(int j = 1;j <= cnt && prime[j]*i <= n;j++){
vis[i*prime[j]] = 1;
if(i % prime[j] == 0) break;
mu[i*prime[j]] = -mu[i];
}
}
for(int i = 1;i <= n;i++){
sum[i] = sum[i-1] + mu[i];
}
}

int f(int a,int b){ //f(1)
int res = 0;
for(int i = 1,key;i <= a && i <= b;i = key + 1){
key = min(a/(a/i),b/(b/i));
res += (a/i)*(b/i)*(sum[key] - sum[i-1]);
}
return res;
}

int main(){
int n,a,b,c,d,k;
scanf("%d",&n);
while(n--){
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
printf("%d\n",f(b,d)-f(a-1,d)-f(c-1,b)+f(a-1,c-1));
}
}

B - 仪仗队

链接

开始没有找到规律,其实就是对于坐标 $(x,y)$ 来说,如果 $gcd(x,y) == 1$ ,则可以被看到

思路1:

也就是说

于 $x \in [1,N] $ , $y \in [1,N] $ ,使得 $gcd(x,y) == $ 1的 $(x,y)$ 的对数

也就是第一题目的 $f(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
/*
给定 a,b c,d , k
求 [a,b] 中的x 和 [c,d] 中的y
满足 gcd(x,y) == k
的对数
*/

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e4 + 10;
int mu[maxn];
int sum[maxn];
int vis[maxn];
int prime[maxn];
int cnt;

void get_mu(int n) { //线性筛
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
prime[++cnt] = i;
mu[i] = -1;
}
for (int j = 1; j <= cnt && prime[j] * i <= n; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
mu[i * prime[j]] = -mu[i];
}
}
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + mu[i];
}
}

int f(int a, int b) { //f(1)
int res = 0;
for (int i = 1, key; i <= a && i <= b; i = key + 1) {
key = min(a / (a / i), b / (b / i));
res += (a / i) * (b / i) * (sum[key] - sum[i - 1]);
}
return res;
}

int main() {
int n;
scanf("%d", &n);
get_mu(maxn);
printf("%d\n", f(n-1, n-1)+2);
}

思路2:

就是筛欧拉函数的前缀和

线性筛:(筛欧拉函数和莫比乌斯函数)板子

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
/*
欧拉函数和莫比乌斯函数的线筛
*/

#include<bits/stdc++.h>
using namespace std;

//#define int long long

const int maxn = 1e5 + 10;

int vis[maxn];
int cnt, prime[maxn];
int mu[maxn], phi[maxn];
int sum_mu[maxn], sum_phi[maxn];

void get(int n) {
sum_mu[1] = sum_phi[1] = mu[1] = phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
prime[++cnt] = i;
phi[i] = i - 1;
mu[i] = -1;
}
for (int j = 1; j <= cnt && prime[j] * i <= n; j++) {
vis[prime[j] * i] = 1;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
mu[i * prime[j]] = -mu[i];
}
}
for (int i = 2; i <= n; i++) {
sum_mu[i] = sum_mu[i - 1] + mu[i];
sum_phi[i] = sum_phi[i - 1] + phi[i];
}
}
signed main() {
get(maxn);

int n; cin >> n;
cout << sum_phi[n-1] * 2 + 1 << endl;
}

杜教筛 板子:

所以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int w[maxn];

int dsjphi(int n) {
if (w[n])return w[n];
int ans = (n + 1) * n / 2;
for (int i = 2, r; i <= n; i = r + 1) {
r = n / (n / i);
ans -= (r - i + 1) * dsjphi(n / i);
}
return w[n] = ans;
}

signed main() {
int n; cin >> n;
cout << dsjphi(n - 1) * 2 + 1 << endl;
}

杜教筛真的很神奇