2022.8.8好题选讲(数论场)

T1 反素数

  传送门：[POI2001][HAOI2007] 反素数

  $tag$：暴力 dfs ？？？

分析

  我们首先没有思路，于是考虑拿出一个数 $n$ 对她进行质因数分解：

$$n=\prod p_i^{k_i}$$

  再经过一些观察可以发现，如果对于 $p_i$ 从小到大排序过后，对于一个反素数而言， $k_i$ 是单调不增的。

  这个其实挺好证明的，因为如果 $k_i$ 单调递增了（$k_i>k_{i-1}$），那么我们交换 $k_i$ 和 $k_{i-1}$，那么我们就得到了一个因数个数与原数相同的且值比原数小的数 $n^{\prime }$，这样一来 $n$ 就不满足反素数的定义了，证毕。

  于是我们可以得出一个性质，那么就是 $1e9$ 反素数一定由前 $10$ 个质数组成（这个很显然吧）。那么我们就可以愉快的 $dfs$ 了，就是尝试确定每一个质数的指数，同时记录一个约数个数就好了。

代码

#include
using namespace std;
#define in 

int n = 0;
int mx = 0;
int ans = 0;
int p[11] = { 0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 19 };

void dfs(int m, int ind, int num, int k){               // 当前数 当前质数编号 当前约数个数 当前指数 
	if(num > mx or (num == mx and m < ans)) ans = m, mx = num;
	int j = 0, temp, i = m;
	while(j < k){
		j++;
		if(n / i < p[ind]) break;
		temp = num * (j + 1), i = i * p[ind];
		if(i <= n) dfs(i, ind + 1, temp, j);
	}
}

signed main(){
	cin >> n;
	dfs(1, 1, 1, 30);
	cout << ans << '\n';
	return 0;
}
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

T2 余数求和

  传送门：[CQOI2007]余数求和

  $tag$：模运算转加减乘除？？？

分析

  直接推式子：

∑ i = 1 n k m o d    i = ∑ i = 1 n k − i × ⌊ k i ⌋ = n k − ∑ i = 1 n i × ⌊ k i ⌋

==​i=1∑n​kmodii=1∑n​k−i×⌊ik​⌋nk−i=1∑n​i×⌊ik​⌋​

  然后我们发现后面那一坨： $\sum _{i=1}^{n}i\times \lfloor \frac{k}{i}\rfloor$ 可以整除分块，然后就可以 $O(\sqrt{n})$ 做完了。

代码

#include
using namespace std;
#define int long long

int ans = 0;
int n = 0; int k = 0;

signed main(){
	cin >> n >> k;
	ans += n * k;
	for(int l = 1, r; l <= n; l = r + 1){
		if(k / l != 0) r = min(n, k / (k / l));
		else r = n;
		ans -= (k / l) * (l + r) * (r - l + 1) / 2;
	}
	cout << ans << '\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

T3 yy 的 gcd

  传送门：yy 的 gcd

  $tag$：莫比乌斯反演？？？

分析

  求得答案就是（$prime$ 表示质数集）：

$$ans=\sum _{i=1}^n\sum _{j=1}^m[\gcd (i,j)\in prime]$$

  我们把他化简成能莫反的形式：

a n s = ∑ k ∈ p r i m e ∑ i = 1 n ∑ j = 1 m [ gcd ⁡ ( i , j ) = k ] = ∑ k = ∈ p r i m e ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ [ gcd ⁡ ( i , j ) = 1 ]

ans==​k∈prime∑​i=1∑n​j=1∑m​[gcd(i,j)=k]k=∈prime∑​i=1∑⌊kn​⌋​j=1∑⌊km​⌋​[gcd(i,j)=1]​

  然后就是喜闻乐见的莫反环节了：

= ∑ k = ∈ p r i m e ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ ∑ d ∣ gcd ⁡ ( i , j ) μ ( d )

=​k=∈prime∑​i=1∑⌊kn​⌋​j=1∑⌊km​⌋​d∣gcd(i,j)∑​μ(d)​

  再然后就是一些小 $trick$ 了：

= ∑ k = ∈ p r i m e ∑ d = 1 ⌊ n k ⌋ ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ [ d ∣ i ∧ d ∣ j ] μ ( d ) = ∑ k = ∈ p r i m e ∑ d = 1 ⌊ n k ⌋ ⌊ n k d ⌋ ⌊ m k d ⌋ μ ( d )

==​k=∈prime∑​d=1∑⌊kn​⌋​i=1∑⌊kn​⌋​j=1∑⌊km​⌋​[d∣i∧d∣j]μ(d)k=∈prime∑​d=1∑⌊kn​⌋​⌊kdn​⌋⌊kdm​⌋μ(d)​

  然后我们发现好像式子已经化到最简了，但是我们算一下复杂度就会发现我们愉快的 $T$ 掉了。所以说这里又有一个常用的降复杂度的 $trick$：令 $T=kd$，然后：

a n s = ∑ k = ∈ p r i m e ∑ d = 1 ⌊ n k ⌋ ⌊ n T ⌋ ⌊ m T ⌋ μ ( d )

ans=​k=∈prime∑​d=1∑⌊kn​⌋​⌊Tn​⌋⌊Tm​⌋μ(d)​

  然后考虑枚举 $T$，并把 $T$ 有关的提到前面去：

$$=\sum _{T=1}^n\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor \sum _{k|T\wedge k\in prime}\mu (\frac{T}{k})$$

  然后我们发现后面 $\sum _{k|T\wedge k\in prime}\mu (\frac{T}{k})$ 可以预处理，具体来说对于每一个质数 $k$ 枚举 $k$ 的倍数 $T$，然后把她的值加上 $\mu (\frac{T}{k})$ 就好了。

代码

#include
using namespace std;
#define in read() 
#define MAXN 10000010

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int Q = 0;
int n = 0; int m = 0;

int cnt = 0;
int flag[MAXN] = { 0 };
int mu[MAXN] = { 0 };
int prime[MAXN] = { 0 };
long long f[MAXN] = { 0 };
long long sum[MAXN] = { 0 };
void sieve(){
	mu[1] = 1;
	for(int i = 2; i <= MAXN; i++){
		if(!flag[i]) prime[++cnt] = i, mu[i] = -1;
		for(int j = 1; j <= cnt and i * prime[j] <= MAXN; j++){
			flag[i * prime[j]] = 1;
			if(i % prime[j] == 0) break;
			mu[i * prime[j]] = -mu[i];
		}
	}
	for (int i = 1; i <= cnt; i++)
        for (int j = 1; prime[i] * j <= MAXN; j++)
            f[j * prime[i]] += mu[j];
    for (int i = 1; i <= MAXN; i++)
        sum[i] = sum[i - 1] + f[i];
}

long long solve(int a,int b) {
    long long ans = 0;
    if (a > b) swap(a, b);
    for (int l = 1, r; l <= a; l = r + 1) {
        r = min(a / (a / l), b / (b / l));
        ans += (sum[r] - sum[l - 1]) * (a / l) * (b / l);
    }
    return ans;
}

signed main(){
	Q = in;
	sieve();
	while(Q--){
		n = in; m = in;
		if(n > m) swap(n, m);
		cout << solve(n, m) << '\n';
	}
	return 0;
}
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

T4 dkw 的 lcm

  传送门：dkw 的 lcm

  $tag$：把数看成希尔伯特空间？？？

分析

  直接把式子告诉你了：

$$ans=\prod _{i_1=1}^n\prod _{i_2=1}^n\cdots \prod _{i_k=1}^n\phi (lcm(i_1,i_2,i_3,\cdots ,i_k))\mathrm{mod}(1e9+7)$$

  首先 $tag$ 里面的希尔伯特空间是个啥？简单来说无限维的空间就可以理解成一个希尔伯特空间。那么这个空间是怎么定义的呢？对于一个数 $n$ 对他质因数分解，然后希尔伯特空间中的维度就代表质因子的次数。

  于是每一个数字 $n$ 就能被看成希尔伯特空间中的一个向量。

  这样做的好处是什么呢？因为这样一来我们复杂的 $lcm$ 操作就变成了对于很多的无限维向量，在每一个维度上取一个最大值，得到的新的数就是这些 $n$ 维向量所代表的数的 $lcm$。

  根据这个思想，我们就很容易想到把质因子单独拎出来考虑贡献（而且 $\phi (n)$ 还是积性函数）。所以我们直接考虑每一个 $\phi (p^t)$ 在最终的答案中出现的次数。然后这个就考虑容斥一下嘛，定义一下三个集合：

1. A = { x ∣ p t ∤ x , x ≤ n } A = \{ x \mid p^t \nmid x, x \leq n \} A={x∣pt∤x,x≤n} 也就是 $1\sim n$ 中不是 $p^t$ 的倍数的数的集合
2. B = { x ∣ p t ∣ x , p t + 1 ∤ x , x ≤ n } B = \{ x \mid p^t \mid x, p^{t + 1} \nmid x, x \leq n \} B={x∣pt∣x,pt+1∤x,x≤n} 也就是 $1\sim n$ 中刚好是 $p^t$ 的倍数的集合
3. C = { x ∣ p t + 1 ∣ x , x ≤ n } C = \{ x \mid p^{t + 1} \mid x, x \leq n \} C={x∣pt+1∣x,x≤n} 也就是超过了 $p^t$

  那么 $\phi (p^t)$ 出现的次数就是：

$$(|A|+|B|{)}^k-|A{|}^k$$

  然后我们考虑 $|A|+|B|$ 等于多少，首先显然等于 $n-|C|$，那么我们考虑 $|C|$ 是多少。这个也就很显然了嘛，因为 $C$ 中只有 $p^{t+1}$ 的倍数，所以个数就是 $\lfloor \frac{n}{p^{t+1}}\rfloor$。

  那么同理，我们就可以得到：

∣ A ∣ = n − ⌊ n p t ⌋ ∣ B ∣ = ⌊ n p t ⌋ − ⌊ n p t + 1 ⌋ ∣ C ∣ = ⌊ n p t + 1 ⌋

∣A∣=∣B∣=∣C∣=​n−⌊ptn​⌋⌊ptn​⌋−⌊pt+1n​⌋⌊pt+1n​⌋​

  然后这里有一个细节，就是因为 $(|A|+|B|{)}^k-|A{|}^k$ 这个东西是写在指数上的，所以根据扩展欧拉定理，运算的时候是对 $1e9+6$ 取模而不是对 $1e9+7$ 取模。

  于是我们枚举 $p$，然后枚举 $t$，然后计算 ${\left(n-\lfloor \frac{n}{p^{t+1}}\rfloor \right)}^k-{\left(n-\lfloor \frac{n}{p^t}\rfloor \right)}^k$，这个就快速幂 $O(\log k)$ 搞定。然后前面枚举的复杂度就是质数的小于等于 $n$ 的 若干次方的个数也就是 $O(\frac{n}{\ln n})$（质数个数也是 $O(\frac{n}{\ln n})$）。于是总的复杂度就是：$O(\frac{n}{\ln n}\log k)$ 的。

T5 lcm sum

  传送门：SP5971 LCMSUM - LCM Sum

  $tag$：还是莫反？？？

分析

  就直接推式子呗：

a n s = ∑ i = 1 n l c m ( i , n ) = ∑ i = 1 n i n gcd ⁡ ( i , n ) = n ∑ i = 1 n i gcd ⁡ ( i , n ) = n ∑ d ∣ n ∑ i = 1 n i d [ d = gcd ⁡ ( i , n ) ]

ans====​i=1∑n​lcm(i,n)i=1∑n​gcd(i,n)in​ni=1∑n​gcd(i,n)i​nd∣n∑​i=1∑n​di​[d=gcd(i,n)]​

  这里注意到满足 $d=\gcd (i,n)$ 的 $i$ 一定是 $d$ 的倍数，所以这里我们考虑改为枚举 $\frac{i}{d}$ 的值：

= n ∑ d ∣ n ∑ i d = 1 n d i d [ d = gcd ⁡ ( i , n ) ] = n ∑ d ∣ n ∑ i = 1 n d i [ d = gcd ⁡ ( i d , n ) ] = n ∑ d ∣ n ∑ i = 1 n d i [ gcd ⁡ ( i , n d ) = 1 ] = n ∑ d ∣ n ∑ i = 1 d i [ gcd ⁡ ( i , d ) = 1 ]

====​nd∣n∑​di​=1∑dn​​di​[d=gcd(i,n)]nd∣n∑​i=1∑dn​​i[d=gcd(id,n)]nd∣n∑​i=1∑dn​​i[gcd(i,dn​)=1]nd∣n∑​i=1∑d​i[gcd(i,d)=1]​

  这里看着就很想莫反，但是仔细思考一下发现其实不用，这里面的这一坨：

$$\sum _{i=1}^{d}i[\gcd (i,d)=1]$$

  这个东西的意义就是 $[1,d]$ 中与 $d$ 互质的数字的和，那么这一坨显然就和 $\phi (d)$ 有关，具体怎样有关呢。

  我们发现，如果 $\gcd (i,d)=1$，那么就有 $\gcd (d-i,d)=1$，所以与 $d$ 互质的数成对出现并且两两和为 $d$，那么这一坨求和就显然是：

$$\sum _{i=1}^{d}i[\gcd (i,d)=1]=\frac{d\phi (d)}{2}$$

  那么总的式子就是：

$$ans=\frac{1}{2}n\sum _{d\mid n}d\phi (d)$$

  显然这个函数也是积性的，所以直接线性筛筛 $1e6$ 就完事了。

代码

#include
using namespace std;
#define in read()
#define MAXN 1001000

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int T = 0; int n = 0;
int tot = 0;
int v[MAXN] = { 0 };
int p[MAXN] = { 0 };
int phi[MAXN] = { 0 };
int ans[MAXN] = { 0 };
void sieve(int n){
	phi[1] = 1;
	for(int i = 2; i <= n; i++){
		if(!v[i]) p[++tot] = i, phi[i] = i - 1;
		for(int j = 1; j <= tot and i * p[j] <= n; j++){
			v[j * p[j]] = 1;
			if(i % p[j] == 0) { phi[i * p[j]] = phi[i] * p[j]; break; }
			phi[i * p[j]] = phi[i] * (p[j] - 1);
		}
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; i * j <= n; j++)
			ans[i * j] += j * phi[j] / 2;
	for(int i = 1; i <= n; i++) ans[i] = i * ans[i] + i;
}

int main(){
	T = in;
	sieve(1e6);
	while(T--){
		n = in;
		cout << ans[n] << '\n';
	}
	return 0;
}

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

lcm sum h

数论

数论之神

屠龙勇士

能量采集 noi 2010