51nod 1220 约数之和

· · 个人记录

题目

求

\sum_{i=1}^{n}\sum_{j=1}^{n}\sigma(ij) n \le 10^{10}

首先有个结论

\sigma(ij)=\sum_{x|i}\sum_{y|j}\dfrac{xj}{y}*[(x,y)=1]

证明？这结论是我百度的。

可以类比下

d(ij)=\sum_{x|i}\sum_{y|j}[(x,y)=1]

然后 \dfrac{xj}{y} 拆开下更明显是约数，x\dfrac{j}{y}。

然后我们代入

\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{x|i}\sum_{y|j}\dfrac{xj}{y}*[(x,y)=1] \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{x|i}\sum_{y|j}\dfrac{xj}{y}\sum_{d|(x,y)}\mu(d) \sum_{d=1}^{n}\mu(d)\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{x|i}\sum_{y|j}\dfrac{xj}{y}*[d|(x,y)]

因为 x|i,y|j 且 d|(x,y) 即 d|x,d|y，这个样子我们可以搞掉那个约束条件 [d|(x,y)]。然后来交换下和式。

\sum_{d=1}^{n}\mu(d)\sum_{d|x}\sum_{d|y}\dfrac{x}{y}\sum_{x|i}\sum_{y|j}j

处理下 \sum_{x|i}\sum_{y|j}j

\sum_{x|i}y\sum_{j=1}^{\lfloor{\frac{n}{y}\rfloor}}j=xy\sum_{i=1}^{\lfloor{\frac{n}{x}}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{y}\rfloor}j

等差数列求和带走

\lfloor\dfrac{n}{x}\rfloor y\dfrac{\lfloor\dfrac{n}{y}\rfloor(\lfloor\dfrac{n}{y}\rfloor+1)}{2}

回代

\sum_{d=1}^{n}\mu(d)\sum_{d|x}\sum_{d|y}\dfrac{x}{y}\lfloor\dfrac{n}{x}\rfloor y\dfrac{\lfloor\dfrac{n}{y}\rfloor(\lfloor\dfrac{n}{y}\rfloor+1)}{2}

消掉一些东西并整理下，比如 \dfrac{x}{y} 的 y 可以消去，然后各回各家。

\sum_{d=1}^{n}\mu(d)\sum_{d|x}x\lfloor\dfrac{n}{x}\rfloor\sum_{d|y}\dfrac{\lfloor\dfrac{n}{y}\rfloor(\lfloor\dfrac{n}{y}\rfloor+1)}{2}

然后倍数的套路一波

\sum_{d=1}^{n}\mu(d)d\sum_{x=1}^{\frac{n}{d}}x\lfloor\dfrac{n}{dx}\rfloor\sum_{y=1}^{\frac{n}{d}}\dfrac{\lfloor\dfrac{n}{dy}\rfloor(\lfloor\dfrac{n}{dy}\rfloor+1)}{2}

单独拆来看，首先第一个是可以杜教筛的。

\sum_{x=1}^{\frac{n}{d}}x\lfloor\dfrac{n}{dx}\rfloor

怪怪的，我们记 n'=\dfrac{n}{d}

那么

\sum_{x=1}^{n'}x\lfloor\dfrac{n'}{x}\rfloor

我们发现

\lfloor\dfrac{n'}{x}\rfloor

这个东西就是

\sum_{i=1}^{n'}[i\%x=0]

那么就是 [1,n'] 中 x 的倍数数量，然后乘上 x。

那么

\sum_{x=1}^{n'}x\lfloor\dfrac{n'}{x}\rfloor \sum_{x=1}^{n'}\sigma(x)

再用这个 n' 去代入

\sum_{y=1}^{n'}\dfrac{\lfloor\dfrac{n'}{y}\rfloor(\lfloor\dfrac{n'}{y}\rfloor+1)}{2}

不太会了 qwq

试试把等差数列求和还回去

枚举 i 试试

\sum_{i=1}^{n'}i\sum_{j=1}^{\lfloor\frac{n'}{i}\rfloor}1=\sum_{i=1}^{n'}i\lfloor\frac{n'}{i}\rfloor

咋又是你！

回代

\sum_{d=1}^{n}\mu(d)d(\sum_{x=1}^{\frac{n}{d}}\sigma(x))^2

发现有 \dfrac{n}{d} 外面整个大的可以整除分块。

记

S(n)=\sum_{d=1}^{n}\mu(d)d f(x)=\mu(x)d g(x)=x

那么

(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}\mu(d)d\dfrac{n}{d}=n\sum_{d|n}\mu(d)=n*[n=1]=[n=1]

然后杜教筛（）

对于

\sum\sigma(x)

可以整除分块预处理一部分，再在需要的时候再整除分块。

\sum_{x=1}^{n'}x\lfloor\dfrac{n'}{x}\rfloor $\text{Code} 
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>

#define N (int)(1.6e5+5)
#define ll long long
#define mod (int)(1e9+7)

using namespace std;
ll lrd() {
    ll f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

bool vis[N];
int pri[N>>2],tot;
ll mu[N],ans_d[N];
map<ll,ll>ans_mu;

ll SUM1(ll x) {
    x%=mod;
    return (x*(x+1)/2)%mod;
}

void init() {
    mu[1]=1;
    for(int i=2;i<N;i++) {
        if(!vis[i]) pri[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&i*pri[j]<N;j++) {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) break;
            mu[i*pri[j]]=-mu[i];
        }
    }
    for(int i=1;i<N;i++) mu[i]=(mu[i-1]+i*mu[i])%mod;
    for(int n=1;n<N;n++) {
        for(int l=1,r;l<=n;l=r+1) {
            r=n/(n/l);
            ans_d[n]+=(SUM1(r)-SUM1(l-1))*(n/l);
            ans_d[n]%=mod;
        }
    }
}

ll fpow2(ll x) {
    x%=mod;
    return x*x%mod;
}

ll get_mu(ll x) {
    if(x<N) return mu[x];
    if(ans_mu[x]) return ans_mu[x];
    ll ans=1;
    for(ll l=2,r;l<=x;l=r+1) {
        r=x/(x/l);
        ans-=(SUM1(r)-SUM1(l-1))*get_mu(x/l)%mod;
        ans%=mod;
    }
    return ans_mu[x]=ans;
}

ll get_d(ll x) {
    if(x<N) return ans_d[x];
    ll ans=0;
    for(ll l=1,r;l<=x;l=r+1) {
        r=x/(x/l);
        ans+=(SUM1(r)-SUM1(l-1))*(x/l)%mod;
        ans%=mod;
    } 
    return ans;
}

int main() {
    init();
    ll ans=0,n=lrd();
    for(ll l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans+=(get_mu(r)-get_mu(l-1))*fpow2(get_d(n/l))%mod;
        ans%=mod;
    }
    ans=(ans%mod+mod)%mod;
    printf("%lld",ans);
    return 0;
}