莫反水题

OI
  1. 1. 求$\sum_{i=a}^b\sum_{j=c}^b[\gcd(i,j)=k]$
    1. 1.1. 代码
  2. 2. 求$\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)$
    1. 2.1. 代码
  3. 3. 一些常用的数论函数

终于可以把暑假集训的坑填上了

求$\sum_{i=a}^b\sum_{j=c}^b[\gcd(i,j)=k]$

首先用二维前缀和的思想,拆成四个询问

$$
\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]
$$

然后我们考虑化简一下这个式子

$$
\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]\\
=\sum_{i=1}^{\lfloor\frac n k\rfloor}\sum_{j=1}^{\lfloor\frac m k\rfloor}[\gcd(i,j)=1]\
$$

然后我们注意到后面的那个东西是$1*\mu$,所以我们可以代换一下

$$
\sum_{i=1}^{\lfloor\frac n k\rfloor}\sum_{j=1}^{\lfloor\frac m k\rfloor}\sum_{l|\gcd(i,j)}\mu(l)\
$$

然后我们考虑变换一下求和指标,枚举所有的$l$,计算它们的贡献

$$
\sum_{l=1}^{\min{\lfloor\frac n k\rfloor,\lfloor\frac m k\rfloor}}\mu(l)\lfloor\frac n {lk}\rfloor\lfloor\frac m {lk}\rfloor
$$

然后注意到后面的除法是可以分块计算的,对$\mu$求一个前缀和

就可以$O(\sqrt n)$处理每个询问了

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 10;
int mu[maxn], pre_mu[maxn];
bitset<maxn> vis;
vector<int> pri;
void pre_cal()
{
mu[1] = 1;
for (int i = 2; i <= 5e4; ++i)
{
if (!vis[i])
pri.push_back(i), mu[i] = -1, vis[i] = 1;
for (int j = 0; j < pri.size(); ++j)
{
int k = i * pri[j];
if (k > 5e4) break;
vis[k] = 1;
if (i % pri[j] == 0)
{
mu[k] = 0;
break;
}
mu[k] = -mu[i];
}
}
for (int i = 1; i <= 5e4; ++i)
pre_mu[i] += mu[i] + pre_mu[i - 1];
}
ll cal(int n, int m, int k)
{
ll ans = 0;
n /= k, m /= k;
if (n > m) swap(n, m);
for (int i = 1, lst = 0; i <= n; i = lst + 1)
{
lst = min(n / (n / i), m / (m / i));
ans += (ll)(n / i) * (m / i) * (pre_mu[lst] - pre_mu[i - 1]);
}
return ans;
}
int main()
{
pre_cal();
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
int a, b, c, d, k;
scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
printf("%lld\n", cal(b, d, k) - cal(a - 1, d, k) - cal(b, c - 1, k) + cal(a - 1, c - 1, k));
}
}

求$\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)$

也就是暑假集训时候的题

$$
\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\\
=\sum_{k=1}^{\min{n\ m}}k\sum_{i=1}^{\lfloor\frac n k\rfloor}\sum_{j=1}^{\lfloor\frac m k\rfloor}[\gcd(i,j)=1]\\
=\sum_{k=1}^{\min{n\ m}}k\sum_{i=1}^{\lfloor\frac n k\rfloor}\sum_{j=1}^{\lfloor\frac m k\rfloor}\sum_{e|\gcd(i,j)}\mu(e)\\
=\sum_{k=1}^{\min{n\ m}}k\sum_{e=1}^n\mu(e)\lfloor\frac n {ke}\rfloor\lfloor\frac m {ke}\rfloor
$$

然后我们令$K=ke$

$$
\sum_{K=1}^{\min{n\ m}}\sum_{e|K}e\mu(\frac K e)\lfloor\frac n K\rfloor\lfloor\frac m K\rfloor
$$

然后注意到中间是$id*\mu$的形式

因为$id*\mu=\varphi$

所以就变成了
$$
\sum_{K=1}^{\min{n\ m}}\varphi(K)\lfloor\frac n K\rfloor\lfloor\frac m K\rfloor
$$
然后就跟上面的套路一样了

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 10;
const int mod = 998244353;
typedef long long ll;
int phi[maxn];
ll pre_phi[maxn];
bitset<maxn> vis;
vector<int> pri;
ll mmod(ll a)
{
a %= mod;
a += mod;
return a % mod;
}
void pre_cal(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; ++i)
{
if (!vis[i])
pri.push_back(i), vis[i] = 1, phi[i] = i - 1;
for (int j = 0; j < pri.size(); ++j)
{
ll k = pri[j] * i;
if (k > n) break;
vis[k] = 1;
if (i % pri[j] == 0)
{
phi[k] = phi[i] * pri[j];
break;
}
phi[k] = phi[i] * (pri[j] - 1);
}
}
for (int i = 1; i <= n; ++i)
pre_phi[i] += (pre_phi[i - 1] + phi[i]) % mod, pre_phi[i] %= mod;
}
int main()
{
int n, m;
cin >> n >> m;
pre_cal(max(n, m) + 4);
ll ans = 0;
if (n > m) swap(n, m);
for (int i = 1, lst = 0; i <= n; i = lst + 1)
{
lst = min(n / (n / i), m / (m / i));
ans += 1ll * (n / i) * (m / i) * (pre_phi[lst] - pre_phi[i - 1]);
mmod(ans);
}
cout << ans % mod << endl;
}

一些常用的数论函数

$\epsilon(n)=[n=1]$

$1(n)=1$

$id(n)=n$

然后是一些变换

$id=1*\varphi$

$\epsilon=1*\mu$

我们来试着证明一下$id*\mu=\varphi$

其实也没什么证明的。。直接带进去。。
$$
\text{left}=1*\varphi*\mu=\epsilon*\varphi=\varphi=\text{right}
$$