OI - 加权约数和（51nod）

套路只有见过了才是套路

---

# 题面

> Linked 51nod-1584

点击展开/折叠 题面

$T$ 组询问（$T\le50000$），每个询问给定 $N$（$1\le N\le10^6$），求下面的式子对 $10^9+7$ 取模的结果：

$$\sum_{i=1}^N\sum_{j=1}^N\max\{i,j\}\sigma(ij)$$

---

# 解析

反演题不需要解释，直接上柿子（然而发现好像不行）不管怎么说，这里的 $\sigma(ij)$ 看起来就很不舒服，我们希望把 $i,j$ 拆开。

最简单的想法就是拆成 $\sum_{x\mid i}\sum_{y\mid j}xy$，但是很可惜 $\sigma(x)$ 不是完全积性的。什么时候会算重？如果 $xd\mid i,yd\mid j$，则 $xyd$ 这个数会在 $xd\cdot y$ 和 $x\cdot yd$ 这里算两次，于是我们加一个限制：$\gcd(x,\tfrac jy)=1$，这样就可以避免上面这种情况。

也就是：

$$\sigma(ij)=\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,\tfrac jy)=1]xy$$

原式代入变为：

$$\begin{aligned} &\sum_{i=1}^N\sum_{j=1}^N\max\{i,j\}\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,\tfrac jy)=1]xy\\ =&\sum_{i=1}^N\sum_{j=1}^N\max\{i,j\}\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1]\tfrac{xj}{y}\\ =&\sum_{i=1}^N\sum_{j=1}^N\max\{i,j\}\sum_{t\mid i,t\mid j}\sum_{t\mid x,x\mid i}\sum_{t\mid y,y\mid j}\tfrac{xj}{y} \end{aligned}$$

对于“$t\mid i,t\mid x,x\mid i$”这样的限制，我们可以枚举 $x=x’t$，则 $x’\mid \tfrac it$。于是：

$$\begin{aligned} &\sum_{i=1}^N\sum_{j=1}^N\max\{i,j\}\sum_{t\mid i,t\mid j}\mu(t)\sum_{x'\mid\tfrac it}\sum_{y'\mid\tfrac jt}\tfrac{x'tj}{y't}\\ =&\sum_{i=1}^N\sum_{j=1}^N\max\{i,j\}\sum_{t\mid i,t\mid j}\mu(t)t\Big(\sum_{x'\mid\tfrac it}x'\Big)\Big(\sum_{y'\mid\tfrac jt}\tfrac{j}{y't}\Big)\\ =&\sum_{i=1}^N\sum_{j=1}^N\max\{i,j\}\sum_{t\mid i,t\mid j}\mu(t)t\sigma(\tfrac it)\sigma(\tfrac jt)\\ =&\sum_{t=1}^N\sum_{t\mid i}^N\sum_{t\mid j}^N\max\{i,j\}\mu(t)t\sigma(\tfrac it)\sigma(\tfrac jt)\\ =&\sum_{t=1}^N\mu(t)t^2\sum_{i=1}^{\lfloor\tfrac Nt\rfloor}\sum_{j=1}^{\lfloor\tfrac Nt\rfloor}\max\{i,j\}\sigma(i)\sigma(j) \end{aligned}$$

然后 $\max\{i,j\}$ 就很烦，把它拆成 “$\times2-1$” 的形式，强行限制 $j\le i$：

$$\begin{aligned} &\sum_{t=1}^N\mu(t)t^2\Big(2\sum_{i=1}^{\lfloor\tfrac Nt\rfloor}\sum_{j=1}^ii\sigma(i)\sigma(j)-\sum_{i=1}^{\lfloor\tfrac Nt\rfloor}i\sigma^2(i)\Big)\\ =&\sum_{t=1}^N\mu(t)t^2\Big(2\sum_{i=1}^{\lfloor\tfrac Nt\rfloor}i\sigma(i)\sum_{j=1}^i\sigma(j)-\sum_{i=1}^{\lfloor\tfrac Nt\rfloor}i\sigma^2(i)\Big) \end{aligned}$$

由于有多组询问，而式子中有 $N$，如果每次重新计算，复杂度就会比较大。我们希望最外层枚举 1 到 N，然后用前缀和 $O(1)$ 回答询问。

然后注意到枚举的 $i,t$ 实际上满足的条件是 $it\le N$，所以直接枚举 $T=it$：（令 $S(x)=\sum_{i=1}^x\sigma(i)$）

$$\begin{aligned} &\sum_{T=1}^N\sum_{t\mid T}\mu(t)t^2\Big(2\cdot\tfrac Tt\cdot\sigma(\tfrac Tt)\cdot S(\tfrac Tt)-\tfrac Tt\cdot\sigma^2(\tfrac Tt)\Big) \end{aligned}$$

令 $F(T)=\sum_{t\mid T}\mu(t)t^2\Big(2\cdot\tfrac Tt\cdot\sigma(\tfrac Tt)\cdot S(\tfrac Tt)-\tfrac Tt\cdot\sigma^2(\tfrac Tt)\Big)$，我们发现 $F(T)$ 与 $N$ 无关，相当于是求 $F(T)$ 的前 $N$ 项和。

$\sigma(x)$ 可以用每个数对其倍数作贡献的方法做到调和级数的复杂度，$S(x)$ 可以 $O(n)$ 预处理；同样，$F(T)$ 可以使 $t=1\sim N$ 对其倍数 $T$ 进行贡献，也是调和级数复杂度。

预处理前缀和 $O(1)$ 询问，复杂度 $O(n\log n+T)$。

---

# 源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e6+10,MOD=1e9+7;
#define ci const int &

int nprm;
int mu[N],prm[N/10],sig[N],f[N],g[N],sum[N];
bool vis[N];

inline int Add(ci a,ci b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(ci a,ci b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(ci a,ci b){return 1ll*a*b%MOD;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a),b>>=1;}return r;}
void Init(){
	mu[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i]){
			prm[++nprm]=i;
			mu[i]=MOD-1;
		}
		for(int j=1;j<=nprm && prm[j]*i<N;j++){
			vis[prm[j]*i]=true;
			if(i%prm[j]==0) break;
			mu[prm[j]*i]=Sub(0,mu[i]);
		}
	}
	for(int i=1;i<N;i++)
		for(int j=i;j<N;j+=i)
			sig[j]=Add(sig[j],i);
	for(int i=1;i<N;i++) f[i]=Add(f[i-1],sig[i]);
	for(int i=1;i<N;i++){
		f[i]=Mul(f[i],Mul(i,sig[i]));
		g[i]=Mul(Mul(sig[i],sig[i]),i);
	}
	for(int t=1;t<N;t++){
		int key1=Mul(Mul(t,t),mu[t]);
		for(int T=t;T<N;T+=t){
			int key2=Sub(Add(f[T/t],f[T/t]),g[T/t]);
			sum[T]=Add(sum[T],Mul(key1,key2));
		}
	}
	for(int i=1;i<N;i++) sum[i]=Add(sum[i-1],sum[i]);
}
int main(){
	Init();
	int cas,n;
	scanf("%d",&cas);
	for(int i=1;i<=cas;i++){
		scanf("%d",&n);
		printf("Case #%d: %d\n",i,sum[n]);
	}
	return 0;
}

---

THE END

Thanks for reading!

$$\begin{split} “\ &流沙\ 坠堕\\ &时光\ 也带走\\ &几句耳语让记忆加速转动\\ &升温的此刻\\ &让郁积的悲伤-消-融-\ ”\\ ——&\text{《无人赞颂的旅程》By Days/泠鸢yousa/洛天依} \end{split}$$

> Linked 无人赞颂的旅程-网易云