2022.8.8 Selected Lectures on Good Topics (Number Theory Field)

T1 反素数

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

  $tag$：暴力 dfs ？？？

分析

  The first thing we no idea,于是考虑拿出一个数 $n$ 对她进行质因数分解：

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

  再经过一些观察可以发现,如果对于 $p_i$ 从小到大排序过后,对于一个反素数而言, $k_i$ Is it does not increase monotonically.

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

  于是我们可以得出一个性质,那么就是 $1e9$ The prime number must be led by former $10$ 个质数组成（这个很显然吧）.那么我们就可以愉快的 $dfs$ 了,就是尝试确定每一个质数的指数,同时记录一个约数个数就好了.

代码

#include<bits/stdc++.h>
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){
                   // 当前数 The current prime number The few number 当前指数 
	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;
}

T2 余数求和

  传送门：[CQOI2007]余数求和

  $tag$：Modular arithmetic？？？

分析

  Direct push formula：

$$\begin{array}{rl}& \sum _{i=1}^{n}k\mathrm{mod}i\\ =& \sum _{i=1}^{n}k-i\times \lfloor \frac{k}{i}\rfloor \\ =& nk-\sum _{i=1}^{n}i\times \lfloor \frac{k}{i}\rfloor \end{array}$$

  turn addition, subtraction, multiplication, and divisionAnd then we found the back那一坨： $\sum _{i=1}^{n}i\times \lfloor \frac{k}{i}\rfloor$ 可以整除分块,然后就可以 $O(\sqrt{n})$ 做完了.

代码

#include<bits/stdc++.h>
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;
}

T3 yy 的 gcd

  传送门：yy 的 gcd

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

分析

  Get the answer is（$prime$ Said prime set）：

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

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

$$\begin{array}{rl}ans=& \sum _{k\in prime}\sum _{i=1}^n\sum _{j=1}^m[\gcd (i,j)=k]\\ =& \sum _{k=\in prime}\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }[\gcd (i,j)=1]\end{array}$$

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

$$\begin{array}{rl}=& \sum _{k=\in prime}\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }\sum _{d|\gcd (i,j)}\mu (d)\end{array}$$

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

$$\begin{array}{rl}=& \sum _{k=\in prime}\sum _{d=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }[d|i\wedge d|j]\mu (d)\\ =& \sum _{k=\in prime}\sum _{d=1}^{\lfloor \frac{n}{k}\rfloor }\lfloor \frac{n}{kd}\rfloor \lfloor \frac{m}{kd}\rfloor \mu (d)\end{array}$$

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

$$\begin{array}{rl}ans=& \sum _{k=\in prime}\sum _{d=1}^{\lfloor \frac{n}{k}\rfloor }\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor \mu (d)\end{array}$$

  Then consider the enumeration $T$,并把 $T$ The mentioned ahead：

$$=\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})$$

  turn addition, subtraction, multiplication, and divisionAnd then we found the back $\sum _{k|T\wedge k\in prime}\mu (\frac{T}{k})$ 可以预处理,具体来说对于每一个质数 $k$ 枚举 $k$ 的倍数 $T$,And then put her value, $\mu (\frac{T}{k})$ 就好了.

#include<bits/stdc++.h>
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;
}

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$ Prime factors decomposition to him,然后希尔伯特空间中的维度就代表质因子的次数.

  So each Numbers $n$ 就能被看成希尔伯特空间中的一个向量.

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

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

1. $A=\{x\mid p^t\nmid x,x\le n\}$ 也就是 $1\sim n$ 中不是 $p^t$ A collection of multiple of the number of
2. $B=\{x\mid p^t\mid x,p^{t+1}\nmid x,x\le n\}$ 也就是 $1\sim n$ 中刚好是 $p^t$ A collection of multiple
3. $C=\{x\mid p^{t+1}\mid x,x\le n\}$ 也就是超过了 $p^t$

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

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

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

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

$$\begin{array}{rl}|A|=& n-\lfloor \frac{n}{p^t}\rfloor \\ |B|=& \lfloor \frac{n}{p^t}\rfloor -\lfloor \frac{n}{p^{t+1}}\rfloor \\ |C|=& \lfloor \frac{n}{p^{t+1}}\rfloor \end{array}$$

  然后这里有一个细节,就是因为 $(|A|+|B|{)}^k-|A{|}^k$ 这个东西是写在指数上的,所以根据扩展欧拉定理,When operation is to $1e9+6$ Modulus instead of $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$,The fast power $O(\log k)$ 搞定.然后前面枚举的复杂度就是质数的小于等于 $n$ 的 若干次方的个数也就是 $O(\frac{n}{\ln n})$（Prime number is $O(\frac{n}{\ln n})$）.于是总的复杂度就是：$O(\frac{n}{\ln n}\log k)$ 的.

T5 数论

数论之神

lcm sum h

lcm sum

屠龙勇士

能量采集 noi 2010