一.莫比乌斯反演公式
$ $
$\qquad\qquad\qquad\qquad\qquad$ 设 $F(n) = \sum\limits_{d|n}f(d)$ ，那么有 $f(n) = \sum\limits_{d|n}\mu(d)F(\frac{n}{d})$
其中 $\mu(d)$ 是这样一个函数：
$\qquad$ $\mu(d)=\begin{cases} 1 , & d=1 \\ (-1)^{k} , & d=\prod\limits_{i=1}^k p_{i} , p_{i} \text{是互异的质数} \\ 0 , & \text{其它情况} \end{cases}$
证明：根据原始 $F(x)$ 定义，$\sum\limits_{d|n}\mu(d)F(\frac{n}{d})$ $=$ $\sum\limits_{d|n}\mu(d)\sum\limits_{d'|\frac{n}{d}}f(d')$
$\qquad\;\;$ 然后根据乘法分配律，我们有 $\qquad\;\;\;=\sum\limits_{d'|n}f(d')\sum\limits_{d|\frac{n}{d'}}\mu(d)$
$\qquad\;\;$ 注意到 $\sum\limits_{d|\frac{n}{d'}}\mu(d)$ 这玩意仅当 $d' = n$ 时为 $1$ ，其余时候都为 $0$
$\qquad\;\;$ 那么 $d'$ 只能等于 $n$ ，原式自然退化成 $f(n)$
书上讲的是些什么东西
二. $\mu$ 函数的性质
- 当且仅当 $n = 1$ 时 $\sum\limits_{d|n}\mu(d) = 1$ ，其余情况下 $\sum\limits_{d|n}\mu(d) = 0$ （ $n$ 是正整数 ）
- 对于任意正整数 $n$ 有 $\sum\limits_{d|n}\frac{\mu(d)}{d} = \frac{φ(n)}{n}$ （ $φ(n)$ 是欧拉函数 ）
三.一些衍生公式
下方有大量 $\LaTeX$ 出没，加载可能较慢
$\;$
$\mathit{0.}$ 前导公式 $\quad\sum\limits_{d|k}[k = 1] = \sum\limits_{d|k}\mu(d)$
$\qquad$ 证明：据性质 $\mathit{1}$ 可得显然成立
$\mathit{0.5}$ 通式 $\quad\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}f(\gcd(i,j))$
$\qquad$ 证明：$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}f(\gcd(i,j))=\sum\limits_{d=1}^{n}f(d)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=d]$
$\qquad\qquad\qquad\qquad\qquad\qquad\;$ $=\sum\limits_{d=1}^{n}f(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor}[\gcd(i,j)=1]$
$\qquad\qquad\qquad\qquad\qquad\qquad\;$ $=\sum\limits_{d=1}^{n}f(d)\sum\limits_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor$
$\qquad\qquad\;\;$ 不妨设 $dk=T$ 那么原式就是 $\sum\limits_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{d|T}f(d)\mu(\frac{T}{d})$
$\qquad\qquad\;\;$ 数论分块可以 $\Theta(n)$ 处理， $\Theta(\sqrt{n})$ 查询
$\mathit{1.}$ 求互质数对数 $\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$[\gcd(i,j)=1]$ $=$ $\sum\limits_{d=1}^n$$\mu$$(d)$$\lfloor$$\frac{n}{d}$$\rfloor$$\lfloor$$\frac{m}{d}$$\rfloor$
$\qquad$ 证明：$\quad\because\quad\sum\limits_{d|k}[k = 1] = \sum\limits_{d|k}\mu(d)$ ，我们用 $\gcd(i,j)$ 去替代 $k$
$\qquad\qquad\quad\;\;\,\therefore$ $\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$[\gcd(i,j)=1]$ $=$ $\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i,d|j}$$\mu(d)$ $\quad\gets$ 这里用了性质 $\mathit{1}$ ，当 $\gcd(i,j)=1$ 时 $\sum\limits_{d|i,d|j}$$\mu(d)$ 才不为 $0$
$\qquad\qquad\qquad\qquad\qquad\qquad\quad\qquad\;\;\;\,$ $=$ $\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|\gcd(i,j)}$$\mu$$(d)$ $\quad\gets$ 这里比较显然，如果 $d$ 既是 $i$ 的因数又是 $j$ 的因数那么 $d$ 一定是 $\gcd(i,j)$ 的因数
$\qquad\qquad\qquad\qquad\qquad\qquad\quad\qquad\;\;\;\,$ $=$ $\sum\limits_{d=1}^n$$\mu$$(d)$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$[d|\gcd(i,j)]$ $\quad\gets$ 根据乘法分配律把 $d$ 扔到前面去，那么此时 $i$ 和 $j$ 都是 $d$ 的倍数才能 $+1$
$\qquad\qquad\qquad\qquad\qquad\qquad\quad\qquad\;\;\;\,$ $=$ $\sum\limits_{d=1}^n$$\mu$$(d)$$\lfloor$$\frac{n}{d}$$\rfloor$$\lfloor$$\frac{m}{d}$$\rfloor$ $\quad\gets$ 可以发现小于等于 $n$ 的 $d$ 的倍数一共有 $\lfloor\frac{n}{d}\rfloor$ 个，同理我们可以搞掉 $m$
$\qquad\qquad\quad\;$ 然后我们就可以用数论分块比较容易地完成了
$\mathit{2.}$ 求最大公约数为 $k$ 的数对个数 $\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$[\gcd(i,j)=k]$ $=$ $\sum\limits_{d=1}^n$$\mu$$(d)$$\lfloor$$\frac{n}{kd}$$\rfloor$$\lfloor$$\frac{m}{kd}$$\rfloor$
$\qquad$ 看上去很熟悉？没错
$\qquad$ 让 $i$ 和 $j$ 同时除以 $k$ 就是 $\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}$$[\gcd(i,j)=1]$
$\mathit{3.}$ 求最大公约数为质数的数对个数 $\quad\sum\limits_{p=1,p\in prime}^{min(n,m)}\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$[\gcd(i,j)=p]$ （ YY的GCD ）
$\qquad$ 就是在上一问里加一个 $\sum\limits_{p=1}^{min(n,m)}(p\in prime)$
$\qquad$ $\quad\sum\limits_{p=1,p\in prime}^{min(n,m)}\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$[\gcd(i,j)=p]$ $=$ $\sum\limits_{p=1,p\in prime}^{n}\sum\limits_{d=1}^{\lfloor\frac{n}{p}\rfloor}$$\mu$$(d)$$\lfloor$$\frac{n}{pd}$$\rfloor$$\lfloor$$\frac{m}{pd}$$\rfloor$
$\qquad$ 不妨设 $T = pd$ 那么有原式 $=$ $\sum\limits_{p=1,p\in prime}^{n}\sum\limits_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$
$\qquad\qquad\qquad\qquad\qquad\qquad\;\;$ $=$ $\sum\limits_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{p|T,p\in prime}\mu(\frac{T}{p})$
$\qquad$ 考虑设 $f(x) = \sum\limits_{p|x,p\in prime}\mu(\frac{x}{p})$ ，原式自然变成 $\sum\limits_{T=1}^{n}f(T)\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$
$\qquad$ 再令 $x$ 的最小质因子是 $y$，即 $x=iy$
$\qquad\qquad$ · $x \in prime$ ：显然有 $f(x) = \mu(1) = 1$
$\qquad\qquad$ · $i \bmod y = 0$ 即在 $x$ 的质因数中 $y$ 出现了不止一次
$\qquad\qquad\qquad$ 当 $i$ 没有多个相同质因子，那么仅当 $p = y$ 时 $\mu(\frac{x}{p}) = \mu(i)$ 不是 $0$ ，$f(x) = \mu(i)$
$\qquad\qquad\qquad$ 当 $i$ 有多个相同质因子，那么对于任何 $p$ 都有 $\mu(\frac{x}{p}) = 0$ ，此时仍有 $\mu(\frac{x}{p})=\mu(i)$ ，因此 $f(x) = \mu(i)}
$\qquad\qquad$ · $i \bmod y \ne 0$ 即在 $x$ 的质因数中 $y$ 仅出现了一次
$\qquad\qquad\qquad$ $f(x) = \sum\limits_{p|x,p\in prime}\mu(\frac{i\times y}{p})\;$ ，$\;$$f(i) = \sum\limits_{p|i,p\in prime}\mu(\frac{i}{p})$，且 $x = i\times y$
$\qquad\qquad\qquad$ 显然的，$f(x)$ 中的每一项（ $\mu(\frac{i\times y}{p})$ ）都是 $f(i)$ 中的某一项（ $\mu(\frac{i}{p})$ ） 的分子乘上一个 $y$ 得来
$\qquad\qquad\qquad$ 又因为 $\mu(x)$ 是积性函数，因此 $\mu(\frac{i\times y}{p})$ $=$ $\mu(\frac{i}{p})\times \mu(y)$ $=$ $-\mu(\frac{i}{p})$
$\qquad\qquad\qquad$ 然鹅发现 $f(x)$ 中还有一个质因子 $y$ ，也就是有一项 $f(i)$ 中没有的 $\mu(\frac{i\times y}{y})$ $=$ $\mu(i)$
$\qquad\qquad\qquad$ $\therefore$ $f(x) = -f(i) + \mu(i)$
$\qquad$ $\therefore$ 我们可以预处理 $f(x)$ ，这样可以在多组数据询问的情况下跑过
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=10010000;
int t,n,m;
int f[WR],sum[WR];
int prime[WR],cnt,miu[WR];
bool flag[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-48;
ch=getchar();
}
return s*w;
}
void Euler(){
miu[1]=1;
for(int i=2;i<WR;i++){
if(!flag[i]) prime[++cnt]=i,miu[i]=-1;
for(int j=1;j<=cnt&&i*prime[j]<WR;j++){
flag[i*prime[j]]=true;
if(i%prime[j]==0){
miu[i*prime[j]]=0;
break;
}
miu[i*prime[j]]=-miu[i];
}
}
for(int i=1;i<=cnt;i++){
for(int j=1;j*prime[i]<WR;j++){
f[prime[i]*j]+=miu[j];
}
}
for(int i=1;i<WR;i++) sum[i]=sum[i-1]+f[i];
}
signed main(){
Euler();
t=read();
while(t--){
int ans=0,pos=0;
n=read(),m=read();
for(int i=1;i<=min(n,m);i=pos+1){
pos=min(n/(n/i),m/(m/i));
ans+=(sum[pos]-sum[i-1])*(n/i)*(m/i);
}
printf("%lld\n",ans);
}
return 0;
}
View Code
$\mathit{4.}$ 求最大公约数为 $k$ 的数对个数 ( 考虑 $i$ 和 $j$ 贡献 ) $\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$ij[\gcd(i,j)=k]$
$\qquad$ 解：$\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$ij[\gcd(i,j)=k]$ $=$ $k^2\sum\limits_{i'=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j'=1}^{\lfloor\frac{m}{k}\rfloor}$$i'j'[\gcd(i',j')=1]$ $\quad\gets$ 这里我们把 $i$ 和 $j$ 都提出了一个 $k$ ，因此 $i = i'\times k$，$j = j'\times k$
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\;$ $\quad$ 又因为要计算 $i$ 和 $j$ 的贡献因此不能像上一个式子一样直接忽略
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad$ $=$ $k^2\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}$$ij\sum\limits_{d|\gcd(i,j)}\mu(d)$ $\quad\gets$ 这里把 $\gcd(i,j)$ 化掉
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad$ $=$ $k^2\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}$$ij[d|\gcd(i,j)]$ $\quad\gets$ 把 $d$ 扔到前面去
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad$ $=$ $k^2\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)d^{2}\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{kd}\rfloor}$$ij$ $\quad\gets$ 这里我们像 $\mathit{1}$ 一样把后面的 $\gcd(i,j)$ 化掉，又因为要计算 $i$ 和 $j$ 的贡献乘一个 $d^2$
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad$ $=$ $k^2\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)d^{2}\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{kd}\rfloor}j$
$\qquad\qquad\;$ 注意到 $\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{kd}\rfloor}j$ 这两项像极了等差数列，于是我们可以设 $f(n)=\sum\limits_{i=1}^{n}=\frac{n(n+1)}{2}$
$\qquad\qquad\;$ 原式 $=$ $k^2\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)d^{2}f(\lfloor\frac{n}{kd}\rfloor)f(\lfloor\frac{m}{kd}\rfloor)$
$\mathit{5.}$ 求 $\gcd$ 之和 $\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$\gcd(i,j)$
$\qquad$ 解：$\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$\gcd(i,j)$ $=$ $\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=k]$ $\quad\gets$ 这里枚举 $\gcd(i,j)$
$\qquad\qquad\qquad\qquad\qquad\quad$ $=$ $\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}$$[\gcd(i,j)=1]$
$\qquad\qquad\qquad\qquad\qquad\quad$ $=$ $\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}$$[\gcd(i,j)=1]$
$\qquad\qquad\qquad\qquad\qquad\quad$ $=$ $\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}$$\sum\limits_{d|\gcd(i,j)}\mu(d)$$\qquad\qquad\qquad\qquad\qquad\quad$ $=$ $\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor$
$\qquad$ 但是还有更优秀的解法 $\qquad$ 解：根据性质 $\mathit{2}$ $\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$\gcd(i,j)$ $=$ $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|\gcd(i,j)}φ(d)$ $\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\;$ $=$ $\sum\limits_{d=1}^{n}φ(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$ $\quad\gets$ 根据公式 $\mathit{1}$ 可得$\mathit{6.}$ 求 $\operatorname{lcm}$ 之和 $\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$\operatorname{lcm}(i,j)$ （Crash的数字表格/JZPTAB）
$\qquad$ 解：$\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$\operatorname{lcm}(i,j)$ $=$ $\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$\frac{ij}{\gcd(i,j)}$ $\qquad\qquad\qquad\qquad\qquad\quad$ $=$ $\sum\limits_{k=1}^{n}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{ij}{k}[\gcd(i,j)=k]$ $\quad\gets$ 这里像 $\mathit{4}$ 一样枚举 $k$ $\qquad\qquad\qquad\qquad\qquad\quad$ $=$ $\sum\limits_{k=1}^{n}\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}\frac{(i\times k)(j\times k)}{k}[\gcd(i,j)=1]$ $\qquad\qquad\qquad\qquad\qquad\quad$ $=$ $\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij[\gcd(i,j)=1]$ $\qquad\qquad\qquad\qquad\qquad\quad$ $=$ $\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij\sum\limits_{d|\gcd(i,j)}\mu(d)$ $\quad\gets$ 换成 $\mu(d)$ $\qquad\qquad\qquad\qquad\qquad\quad$ $=$ $\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}\mu(d)(\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}i[d|i])(\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}j[d|j])$$\qquad\qquad\qquad\qquad\qquad\quad$ $=$ $\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}\mu(d)(d\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i)(d\sum\limits_{j=1}^{\lfloor\frac{m}{kd}\rfloor}j)$ $\quad\gets$ 提出 $d$ $\qquad\qquad\qquad\qquad\qquad\quad$ $=$ $\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}d^{2}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{kd}\rfloor}j$ $\qquad\qquad\quad$ 我们还是可以设 $f(i) = \frac{i(i+1)}{2}$，于是就可以暂时把它优化到 $\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}d^{2}\mu(d)f(\lfloor\frac{n}{kd}\rfloor)f(\lfloor\frac{m}{kd}\rfloor)$ ，这是一个 $O(n)$ 算法 $\qquad\qquad\quad$ 但是如果有 $M$ 组询问我们需要一个 $O(M\sqrt{n})$ 的算法 $\qquad\qquad\quad$ 我们设 $T = kd$ ，可以发现前面那一堆 $\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}d^{2}\mu(d)$ $=$ $\sum\limits_{d=1}^{n}d^{2}\mu(d)\sum\limits_{k=1}^{n}k$ $\qquad\qquad\quad$ 因为我们枚举了 $T$ 也就相当于 $k = \frac{T}{d}$ ，所以原式 $=$ $\sum\limits_{d=1}^{n}d^{2}p$ $=$ $T\sum\limits_{d=1}^{n}d$ $\qquad\qquad\quad$ 但是可以发现 $d$ 必须满足 $d|T$ 否则 $k$ 将不是整数，我们可以把后面的式子进一步化成 $T\sum\limits_{d|T}d$ $\qquad\qquad\quad$ $\therefore$ $\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}d^{2}\mu(d)f(\lfloor\frac{n}{kd}\rfloor)f(\lfloor\frac{m}{kd}\rfloor)$ $=$ $\sum\limits_{T=1}^{n}Tf(\lfloor\frac{n}{kd}\rfloor)f(\lfloor\frac{m}{kd}\rfloor)\sum\limits_{d|T}d\mu(d)$ $\qquad\qquad\quad$ 观察可得只有 $g(T) = \sum\limits_{d|T}d\mu(d)$ 这一块是有难度的，考虑狄利克雷卷积 $\qquad\qquad\quad$ 设 $T = \prod\limits_{i=1}^k p_{i}^{\alpha_{i}} ( p_{i} 为互异素数) $ ，显然 $g(T)$ 是一个积性函数，可以把它卷成 $g(T) = \prod\limits_{i=1}^{k}g(p_{i}^{\alpha_{i}}) = \prod\limits_{i=1}^{k}(1-p_{i})$ $\qquad\qquad\quad$ $\therefore$ $\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$\operatorname{lcm}(i,j)$ $=$ $\sum\limits_{T=1}^{n}Tg(T)f(\lfloor\frac{n}{kd}\rfloor)f(\lfloor\frac{m}{kd}\rfloor)$ $\qquad\qquad\quad$ 可以预处理 $T\times g(T)$ 前缀和，在线性筛内完成
#include<cstdio>
#include<cstring>
#include<string>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=10010000,mod=100000009;
int n,m,ans;
int f[WR];
int prime[WR],cnt,miu[WR];
bool flag[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-48;
ch=getchar();
}
return s*w;
}
void Euler(){
miu[1]=1,f[1]=1;
for(int i=2;i<WR;i++){
if(!flag[i]) prime[++cnt]=i,miu[i]=-1,f[i]=-i+1+mod;
for(int j=1;i*prime[j]<WR&&j<=cnt;j++){
flag[i*prime[j]]=true;
if(i%prime[j]==0){
miu[i*prime[j]]=0;
f[i*prime[j]]=f[i];
break;
}
miu[i*prime[j]]=-miu[i];
f[i*prime[j]]=(f[i]*f[prime[j]])%mod;
}
}
for(int i=1;i<WR;i++) f[i]=f[i]*i%mod;
for(int i=1;i<WR;i++) f[i]=(f[i]+f[i-1])%mod;
}
signed main(){
Euler();
int t=read();
while(t--){
ans=0;
n=read(),m=read();
int j=0;
for(int i=1;i<=min(n,m);i=j+1){
j=min(m/(m/i),n/(n/i));
ans=(ans+((n/i)*(n/i+1)/2%mod)*((m/i)*(m/i+1)/2%mod)%mod*(f[j]-f[i-1]+mod)%mod)%mod;
}
printf("%lld\n",(ans+mod)%mod);
}
return 0;
}
View Code
$\mathit{7.}$ 求 $\gcd$ 的幂次方之和 $\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$\gcd(i,j)^k$ （于神之怒加强版）
$\qquad$ 解：$\quad\sum\limits_{i=1}^n\sum\limits_{j=1}^m$$\gcd(i,j)^k$ $=$ $\sum\limits_{p=1}^{n}p^k\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=p]$
$\qquad\qquad\qquad\qquad\qquad\quad\;$ $=$ $\sum\limits_{p=1}^{n}p^k\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}[\gcd(i,j)=1]$
$\qquad\qquad\qquad\qquad\qquad\quad\;$ $=$ $\sum\limits_{p=1}^{n}p^k\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum\limits_{d|\gcd(i,j)}\mu(d)$
$\qquad\qquad\qquad\qquad\qquad\quad\;$ $=$ $\sum\limits_{p=1}^{n}p^k\sum\limits_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}[d|i][d|j]$
$\qquad\qquad\qquad\qquad\qquad\quad\;$ $=$ $\sum\limits_{p=1}^{n}p^k\sum\limits_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor$
$\qquad\qquad$ 不妨设 $T = pd$ ，那么原式 $=$ $\sum\limits_{p=1}^{n}p^k\sum\limits_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$
$\qquad\qquad\qquad\qquad\qquad\qquad\;\;$ $=$ $\sum\limits_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{p|T}^{n}p^k\sum\limits_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)$
$\qquad\qquad\qquad\qquad\qquad\qquad\;\;$ $=$ $\sum\limits_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{p|T}^{n}p^k\mu(\frac{T}{p})$
$\qquad\qquad$ 设 $f(x)$ $=$ $\sum\limits_{p|x}^{n}p^k\mu(\frac{x}{p})$ ，那么显然的 $f(x)$ 是一个积性函数
$\qquad\qquad$ $\because$ $T = \prod\limits_{i=1}^{num} p_{i}^{\alpha_i}$ $\qquad$ $\therefore$ $f(T) = \prod\limits_{i=1}^{num} f(p_{i}^{\alpha_i})$
$\qquad\qquad$ 可以发现 $f(p^{\alpha}) = p^{\alpha k} - p^{(\alpha-1)k}$ ，因此 $f(T) = \prod\limits_{i=1}^{num}(p_i^{\alpha_i k}-p_i^{\alpha_{i-1} k})$
$\qquad\qquad$ 设 $p_t \in prime$ ，那么 $\frac{f(ap_t)}{f(a)}$ $=$ $\frac{\prod\limits_{i=1}^{num}f(p_i^{\alpha_i + [i=t]})}{\prod\limits_{i=1}^{num}f(p_i^{\alpha_i})}$ $=$ $\frac{f(p_t^{\alpha_t + 1})}{f(p_t^{\alpha_t})}$ $=$ $p_t^k$
$\qquad\qquad$ $\therefore\quad$ $\gcd(a,p_t) ＞ 1$ 时 $f(ap_t) = p_t^kf(a)$ ，同时当 $\gcd(a,p_t) = 1$ 时 $f(ap_t) = f(a)f(p_t)$
#include<cstdio>
#include<cstring>
#include<string>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=10010000,mod=1e9+7;
int t;
int n,m,k,ans;
int pw[WR],f[WR];
int prime[WR],cnt,miu[WR];
bool flag[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-48;
ch=getchar();
}
return s*w;
}
int quick_pow(int a,int b){
int base=a,ans=1;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans;
}
void Euler(){
miu[1]=1,f[1]=1;
for(int i=2;i<WR;i++){
if(!flag[i]){
prime[++cnt]=i,miu[i]=-1;
pw[cnt]=quick_pow(i,k),f[i]=(pw[cnt]-1+mod)%mod;
}
for(int j=1;i*prime[j]<WR&&j<=cnt;j++){
flag[i*prime[j]]=true;
if(i%prime[j]==0){
miu[i*prime[j]]=0;
f[i*prime[j]]=f[i]*pw[j]%mod;
break;
}
miu[i*prime[j]]=-miu[i];
f[i*prime[j]]=(f[i]*f[prime[j]])%mod;
}
}
for(int i=1;i<WR;i++) f[i]=(+f[i]+f[i-1])%mod;
}
signed main(){
t=read(),k=read();
Euler();
while(t--){
n=read(),m=read();
int pos,ans=0;
for(int i=1;i<=min(n,m);i=pos+1){
pos=min(n/(n/i),m/(m/i));
ans=(ans+(f[pos]-f[i-1]+mod)%mod*(n/i)%mod*(m/i)%mod)%mod;
}
printf("%lld\n",ans);
}
return 0;
}
View Code
$\mathit{8.}$ 约数个数和 $\quad\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(ij)$ 其中 $d(i)$ 表示 $i$ 的约数个数
$\qquad$ 解：首先证明 $d(ij) = \sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1]$
$\qquad\quad\;\;\,$ 考虑某一个质因子 $p$
$\qquad\quad\;\;\,$ 若 $i$ 包含 $\lambda$ 个 $p$ ，$j$ 包含 $\mu$ 个 $p$ ，那么显然的 $i\times j$ 包含 $\lambda + \mu$ 个 $p$ ，此时等式左边有 $\lambda + \mu + 1$ 种对 $p$ 的选法
$\qquad\quad\;\;\,$ 同理 $x$ 可以包含 $[0,\lambda ]$ 个 $p$ ，$y$ 可以包含 $[0,\mu ]$个 $p$ ，我们有 $\lambda + \mu + 1$ 种情况满足 $\gcd(x,y) = 1$
$\qquad\quad\;\;\,$ $\quad$ · $\,$$x = 0$ ，$y = 0$ ，贡献是 $1$
$\qquad\quad\;\;\,$ $\quad$ · $\,$$x = 0$ ，$y \in [1,\mu]$ ，贡献是 $\mu$
$\qquad\quad\;\;\,$ $\quad$ · $\,$$x \in [1,\lambda]$ ，$y = 0$ ，贡献是 $\lambda$
$\qquad\quad\;\;\,$ 三者相加就是 $\lambda + \mu + 1$ ，可以得证
$\qquad\quad\;\;\,$ $\therefore$ 原式 $= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y) = 1]$
$\qquad\qquad\qquad\;\;$ $=$ $\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor[\gcd(x,y)=1]$ $\quad\gets$ $[1,n]$ 中 $x$ 的倍数有 $\lfloor\frac{n}{x}\rfloor$ 个，$[1,m]$ 中 $y$ 的倍数有 $\lfloor\frac{m}{y}\rfloor$ 个，可以消掉两个 $\sum$
$\qquad\qquad\qquad\;\;$ $=$ $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[\gcd(i,j)=1]$
$\qquad\qquad\qquad\;\;$ $=$ $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\sum\limits_{d|\gcd(i,j)}\mu(d)$
$\qquad\qquad\qquad\;\;$ $=$ $\sum\limits_{d=1}^{\min(n,m)}\mu(d)\sum\limits_{i=1}^{\frac{n}{d}}\lfloor\frac{n}{di}\rfloor\sum\limits_{j=1}^{\frac{m}{d}}\lfloor\frac{m}{dj}\rfloor$
$\qquad\quad\;\;\,$ 不妨设 $f(x) = \sum\limits_{i=1}^{x}\lfloor\frac{x}{i}\rfloor$
$\qquad\quad\;\;\,$ 那么显然的原式 $= \sum\limits_{d=1}^{\min(n,m)}\mu(d)f(\frac{n}{d})f(\frac{m}{d})$
$\qquad\quad\;\;\,$ 可以 $O(n\sqrt{n})$ 预处理 $f(x)$ ，用 $O(\sqrt{n})$ 查询
#include<cstdio>
#include<cstring>
#include<string>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=100100,mod=1e9+7;
int t;
int n,m,k;
int f[WR],g[WR];
int table[2010][2010];
int prime[WR],cnt,miu[WR];
bool flag[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-48;
ch=getchar();
}
return s*w;
}
int quick_pow(int a,int b){
int base=a,ans=1;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans;
}
void Euler(){
miu[1]=1,g[1]=1,f[1]=1;
for(int i=2;i<WR;i++){
if(!flag[i]){
prime[++cnt]=i;
miu[i]=-1;
f[i]=1,g[i]=2;
}
for(int j=1;i*prime[j]<WR&&j<=cnt;j++){
flag[i*prime[j]]=true;
if(i%prime[j]==0){
g[i*prime[j]]=g[i]/(f[i]+1)*(f[i]+2);
f[i*prime[j]]=f[i]+1;
miu[i*prime[j]]=0;
break;
}
miu[i*prime[j]]=-miu[i];
g[i*prime[j]]=g[i]*g[prime[j]];
f[i*prime[j]]=1;
}
}
for(int i=2;i<WR;i++) miu[i]+=miu[i-1];
for(int i=2;i<WR;i++) g[i]+=g[i-1];
}
signed main(){
Euler();
t=read();
while(t--){
n=read(),m=read();
if(n<=2000&&m<=2000){
if(table[n][m]){
printf("%lld\n",table[n][m]);
continue;
}
}
int pos,ans=0;
for(int i=1;i<=min(n,m);i=pos+1){
pos=min(n/(n/i),m/(m/i));
ans+=(miu[pos]-miu[i-1])*g[n/i]*g[m/i];
}
if(n<=2000&&m<=2000) table[n][m]=table[m][n]=ans;
printf("%lld\n",ans);
}
return 0;
}
View Code
$\mathit{9.}$ 求 $\gcd$ 的约数和之和 $\quad\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sigma_{1}(\gcd(i,j))$（数表）
$\qquad$ 这里的 $\sigma_{1}(x)$ 函数指 $x$ 的约数和
$\qquad$ 那么显然地，我们可以把上面的式子化成 $\sum\limits_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{d|T}\sigma_{1}(d)\mu(\frac{T}{d})$
$\qquad$ 考虑将询问按 $a$ 从小到大排序，枚举询问的时候，$a$ 变大会使得一些 $\sigma_1(d)$ 对 $g(T)$ 产生贡献，我们就用枚举倍数的方法来找到所有的 $T$
$\qquad$ 然后我们需要动态修改 $g(T)$ 的值，支持区间询问，因此可以使用树状数组实现
#include<cstring>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000;
struct Node{
int n,m,a,id;
bool operator<(const Node &b)const{
return a<b.a;
}
}ask[WR<<1];
int tree[WR<<1];
int f[WR<<1];
int prime[WR<<1],cnt,mu[WR<<1];
bool isprime[WR<<1];
pair<int,int>g[WR<<1];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+ch-48;
ch=getchar();
}
return s*w;
}
int lowbit(int x){
return x&(-x);
}
void modify(int k,int val){
for(int i=k;i<WR;i+=lowbit(i)){
tree[i]+=val;
}
}
int query(int k){
int res=0;
for(int i=k;i;i-=lowbit(i)){
res+=tree[i];
}
return res;
}
void sieve(){
mu[1]=1;
g[1]=make_pair(1,1);
for(int i=2;i<WR;i++){
if(!isprime[i]){
prime[++cnt]=i;
mu[i]=-1;f[i]=i+1;g[i]=make_pair(i+1,i);
}
for(int j=1;j<=cnt&&i*prime[j]<WR;j++){
isprime[i*prime[j]]=true;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
f[i*prime[j]]=f[i]*prime[j]+1;
g[i*prime[j]]=make_pair((int)g[i].first/f[i]*f[i*prime[j]],i*prime[j]);
break;
}
mu[i*prime[j]]=-mu[i];
f[i*prime[j]]=prime[j]+1;
g[i*prime[j]]=make_pair(g[i].first*g[prime[j]].first,i*prime[j]);
}
}
}
int solve(int n,int m){
int res=0;
if(n>m) swap(n,m);
for(int i=1,j;i<=n;i=j+1){
j=min(n/(n/i),m/(m/i));
// printf("%lld\n",j);
res=res+(query(j)-query(i-1))*(int)(n/i)*(int)(m/i);
}
return res;
}
int ans[WR];
signed main(){
sieve();
sort(g+1,g+WR);
// for(int i=1;i<=100;i++) printf("%lld %lld\n",g[i].first,g[i].second);
int q=read();
for(int i=1;i<=q;i++){
ask[i].n=read(),ask[i].m=read(),ask[i].a=read(),ask[i].id=i;
}
sort(ask+1,ask+1+q);
for(int i=1,j=1;i<=q;i++){
while(g[j].first<=ask[i].a&&j<WR){
for(int k=g[j].second;k<WR;k+=g[j].second){
modify(k,g[j].first*mu[(int)k/g[j].second]);
}
j++;
}
ans[ask[i].id]=solve(ask[i].m,ask[i].n);
}
int mod=(1<<31);
for(int i=1;i<=q;i++){
printf("%lld\n",ans[i]%mod);
}
return 0;
}
View Code
$\mathit{10.}$ 求 $\gcd$ 所含质因子的最大幂指数之和 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}f(\gcd(i,j))$
$\qquad$ 依旧显然地，我们可以把上面的式子化成 $\sum\limits_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{d|T}f(d)\mu(\frac{T}{d})$
$\qquad$ 不妨设 $h(T)=\sum\limits_{d|T}f(d)\mu(\frac{T}{d})$ ，我们假设 $T$ 被唯一分解为 $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$
$\qquad$ 为了保证有贡献我们要让 $\mu(Td)$ 非零，那么 $Td$ 的最大指数幂不能超过一
$\qquad$ 也就是说枚举的$d=p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}$ 必须满足，对于所有 $i\in [1,k]$ 有 $0\leqslant a_i−b_i \leqslant 1$
$\qquad$ 那么这么来说对于每个 $T$ ，设其一共含有 $k$ 种不同的质因数，那么会给它贡献的就只有 $2^k$ 个数。枚举的每个 $d$，就有 $f(d)=\max\{\beta_i\}$
$\qquad$ 分两种情况讨论：
$\qquad$ 1、存在一组 $i,j$ 使 $\alpha_i<\alpha_j$
$\qquad\qquad$ 那么此时 $\beta_i$ 就永远不可能成为 $\max\{\beta_i\}$ ，换言之，无论你取不取这个 $i$ ，$f(d)$ 的值算出来都是一样的。
$\qquad\qquad$ 又因为取这个 $i$ 的时候的 $\mu(Td)$ 值与不取这个 $i$ 的时候的 $\mu(Td)$ 值恰好相反，所以加起来就会有 $h(T)=0$。
$\qquad$ 2、所有 $\alpha_i$ 都相等
$\qquad\qquad$ 还是装作上一种情况算，不同之处在于当所有 $\beta_i$ 取 $\alpha_i−1$ 的时候$f(d)=\beta_i=\alpha_i−1$
$\qquad\qquad$ 那么这时 $h(T)$ 的值就只与这个 $-1$ 前面的 $\mu$ 值有关（因为其他的都抵消掉了）。
$\qquad\qquad$ 易知这个 $-1$ 前面的系数是 $\mu(p_1p_2\cdots p_k)$，所以说 $h(T)=−(−1)^k=(−1)^{k+1}$
$\qquad$ 线性筛记录每个数的最小质因子的幂指数和最小质因子的指数次幂，判除掉最小质因子后最小值因子的幂指数是否相等
#include<cstring>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=10001000;
int a[WR],h[WR],low[WR],mu[WR];
int prime[WR>>1],cnt;
bool isprime[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+ch-48;
ch=getchar();
}
return s*w;
}
void sieve(){
mu[1]=1;
for(int i=2;i<WR;i++){
if(!isprime[i]){
low[i]=prime[++cnt]=i;
mu[i]=-1;
a[i]=h[i]=1;
}
for(int j=1;j<=cnt&&i*prime[j]<WR;j++){
isprime[i*prime[j]]=true;
if(i%prime[j]==0){
a[i*prime[j]]=a[i]+1;
low[i*prime[j]]=low[i]*low[prime[j]];
if(i==low[i]) h[i*prime[j]]=1;
else h[i*prime[j]]=(a[i/low[i]]==a[i*prime[j]]?-h[i/low[i]]:0);
break;
}
a[i*prime[j]]=1;
low[i*prime[j]]=prime[j];
h[i*prime[j]]=(a[i]==1)?-h[i]:0;
}
}
for(int i=1;i<WR;i++) h[i]+=h[i-1];
}
signed main(){
sieve();
int t=read();
while(t--){
int n=read(),m=read();
if(n>m) swap(n,m);
int ans=0;
for(int i=1,j=1;i<=n;i=j+1){
j=min(n/(n/i),m/(m/i));
ans+=(n/i)*(m/i)*(h[j]-h[i-1]);
}
printf("%lld\n",ans);
}
return 0;
}
View Code
标签：lfloor,frac,limits,qquad,sum,莫比,rfloor,反演,乌斯 From： https://www.cnblogs.com/WintersRain/p/16344737.html