基础数论 整除分块与欧拉函数

整除分块：

例题：

已知 \(f(n) =\sum\limits_{i = 1 }^{n}\left\lfloor\frac{n}{i}\right\rfloor\)，给定 \(n\)，求 \(f(n)\) 的值。

固然可以 \(O(n)\) 暴力，但显然会\(TLE\)。

计算一下前几项的值之后可以发现\(\left \lfloor \frac{n}{i} \right \rfloor\) 的取值在连续的一段区间内是相同的，那么就可以将其分为若干块分别进行计算。

先让 \(l\) 为区间的左端点，那么这块的值都为 \(k = \left\lfloor\frac{n}{l}\right\rfloor\) ， \(r=max(i)=\left\lfloor\frac{n}{k}\right\rfloor\)。将 \(k\) 代入，得到 \(r=\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor\)。这样每一块的左右端点都能用确定的式子得到了。这样分块的值就为单值 $\times $ 区间长度，即 \(k\times (r-l+1)\) 。

模板：

ll division_block(ll n){
	ll res = 0;
    for(ll l = 1, r; l <= n; l = r + 1){
        r = n / (n / l);
        res += n / l * (r - l + 1);
    }
    return res;
}

欧拉函数：

定义：

欧拉函数是指 \(1 \sim N\)​ 中与 \(N\)​ 互质的数的个数，记为 \(\varphi(N)\)​。
即

特别的 \(\varphi(1)=1\)​

性质：

1.若 \(x\)​ 为质数, \(\varphi(x)=x-1\)。

质数除了他本身都与他互质。

2.\(\forall n>1,1\sim n\) 中与 \(n\) 互质的数的和为 \(n\times \varphi(n)/2\) 。

因为 \({\rm gcd}(n,x)=={\rm gcd}(n,n-x)\) ，所以与 \(x\) 不互质的数 \(x,n-x\) 成对出现，平均值为 \(\frac{n}{2}\) ，所以与 \(n\) 互质的数的平均值也是 \(\frac{n}{2}\) ，而这样的数共有 \(\varphi(n)\) 个，故得性质2。

3.若 \(x=p^k(p为质数)\)​ ，则 \(\varphi(x)=(p-1)\times p^{k-1}\)​。

发现所有 \(p\)​ 的倍数都与 \(x\)​ 不互质，其他数都与 \(x\)​ 互质，而 \(p\)​ 的倍数共有 \(p^{k-1}\)​ 个(包括 \(x\)​ )。

故\(\varphi(x)=p^k-p^{k-1}=(p-1)\times p^{k-1}\)​

4.若 \(p,q\) 互质,则 \(\varphi(p\times q)=\varphi(p)\times \varphi(q)\) ，即欧拉函数为积性函数。

如果 \(a\) 与 \(p\) 互质 \((a<p)\) ， \(b\) 与 \(p\) 互质 \((b<q)\) ， \(c\) 与 \(pq\) 互质 \((c<pq)\) ，则 \(c\) 与数对 \((a,b)\) 是一一对应的。

符合条件的 \(a\) 有 \(\varphi(p)\) 种， \(b\) 有 \(\varphi(q)\) 种， 则所对应的 \((a,b)\) 数对有 \(\varphi(p)\varphi(q)\) 种。而符合条件的 \(c\) 有 \(\varphi(pq)\) 种。

所以 \(\varphi(pq)=\varphi(p)\times \varphi(q)\)

5.对于一正整数 \(x=p_1^{c_1}\times p_2^{c_2}\times ...\times p_n^{c_n}\) 有

证明：

\[\varphi(x)=\prod_{i=1}^n\varphi(p_i^{c_i})=\prod_{i=1}^n(p_i-1)\times p_i^{c_i-1}=\prod_{i=1}^np_i^{k_i}\times(1-\frac{1}{p_i})=x\prod_{i=1}^n(1-\frac{1}{p_i}) \]

6.若 \(p\)​ 为 \(x\)​ 的质因数，则 \(\varphi(x\times p)=\varphi(x)\times p\)

\[\varphi(x\times p)=x\times \prod_{i=1}^n(1-\frac{1}{p_i})\times p=\varphi(x)\times p\\ (p\in [p_i]) \]

7.若质数 \(p\) 不是 \(x\) 的因数，则 \(\varphi(x\times p)=\varphi(x)\times (p-1)\)

\[\varphi(x\times p)=\varphi(x)\times \varphi(p)=\varphi(x)\times(p-1) \]

设 \(f(n)=\sum_{d\mid n}\varphi(d)\)

\(\therefore f(a\times b)=\sum_{d\mid ab}\varphi(d)\)

\(当{\rm gcd}(a,b)=1时:\) \({\rm gcd}(\forall d_i\mid a,\forall d_i\mid b )=1\)

\(\therefore \sum_{d\mid ab}\varphi(d)=\sum_{d\mid a}\varphi(d)\times \sum_{d\mid b}\varphi(d)\)

​ 即 \(f(a\times b)=f(a)\times f(b)\)​​​​

\(\therefore f(p^m)=\sum_{f\mid p^m}\varphi(d)=\sum_{i=0}^m\varphi(p^i)=1+\sum_{i=0}^{m-1}(p-1)\times p^i(p为质数)\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ =1+(p-1)\times (1+p+\cdots+p^{m-1})\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ =1+(p-1)\times \frac{1-p^m}{1-p}=p^m\)

\(\therefore f(p^m)=p^m\)

\(\therefore f(n)=f(\prod_{i=1}^np_i^{c_i})=\prod_{i=1}^nf(p_i^{c_i})=\prod_{i=1}^np_i^{c_i}=n\)

\(\therefore \sum_{d\mid n}\varphi(d)=n\)

代码：

1.求解单个欧拉函数：利用性质 \(5\) ，时间复杂度 \(O(\sqrt n)\) 。

int phi(int n) {
	int ans = n;
	int t = sqrt(n);
	for(int i=2; i<=t; ++i) {
		if(n%i == 0)
			ans = ans/i*(i-1);
		while(n%i == 0) n /= i;
	}
	if(n > 1) ans = ans/n/(n-1);
	return ans;
}

2. 埃氏筛求 \(1\sim n\)的欧拉函数值，时间复杂度 \(O(n \log n)\)

void found_euler(int n) {
	for(int i=1; i<=n; ++i) phi[i] = i;
	for(int i=2; i<=n; ++i) {
		if(phi[i] == i) { // i为质数 
			for(int j=i; j<=n; j+=i) // 给包含质因子i的数字，乘上 (1-1/i) 
				phi[j] = phi[j]/i*(i-1); 
		}
	}
} 

3.欧拉筛求 \(1\sim n\) 的欧拉函数值，时间复杂度 \(O(n)\)

int phi[N],pr[N],cnt;
bool vis[N];
void init(){
	int n=1e5+50;
	phi[1]=1; 
	for(int i=2;i<=n;i++){
		if(!vis[i]){pr[++cnt]=i,phi[i]=i-1;}
		for(int j=1;j<=cnt&&pr[j]<=n/i;j++){
			vis[i*pr[j]]=1;
			phi[i*pr[j]]=phi[i]*((i%pr[j])?pr[j]-1:pr[j]); 
			if(i%pr[j]==0)break;
		} 
	}
}

GCD SUM

求

原式可化为

\[\begin{array}{l} =\sum_{i=1}^n\sum_{j=1}^n\sum_{d\mid\gcd(i,j)}\varphi(d)\\ =\sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^n\varphi(d)[d\mid i][d\mid j]\\ =\sum_{d=1}^n\varphi(d)\sum_{i=1}^n\sum_{j=1}^n[d\mid i][d\mid j]\\ =\sum_{d=1}^n\varphi(d)\lfloor\frac{n}{d}\rfloor^2 \end{array} \]

GCD：

给定正整数 \(n\) 求 \(1\leq x,y\leq n\&\& \gcd(x,y)\in prime\) 的数对有多少。

\[\begin{array}{l} =\sum_{p\in prime}\sum_{i=1}^n\sum{j=1}^n[gcd(i,j)=p]\\ =\sum_{p\in prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum{j=1}^{\lfloor\frac{n}{p}\rfloor}[gcd(i,j)=1]\\ =\sum_{p\in prime}(\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}(2\times\sum{j=1}^i[gcd(i,j)=1])-1)\\ =\sum_{p\in prime}(2\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i)-1) \end{array} \]

Longge 的问题

求

\[\begin{array}{l} =\sum_{i=1}^n\gcd(i,n)\\ =\sum_{d\mid n}d\times\sum_{i=1}^n[\gcd(i,n)=d]\\ =\sum_{d\mid n}d\times\sum{i=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i,\frac{n}{d})=1]\\ =\sum_{d\mid n}d\times \varphi(\frac{n}{d}) \end{array} \]

by ysx