「51nod1220」 约数之和 题解

本文主要是介绍「51nod1220」 约数之和 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Statement

\(\sigma(k)\) 表示 \(k\) 的所有约数的和。\(\sigma(6) = 1 + 2 + 3 + 6 = 12\)

定义 \(S(N) = ∑_{i=1}^N ∑_{j=1}^N \sigma(i*j)\)

给出正整数 \(N\)，求 \(S(N)\) ，由于结果可能会很大，输出 $\mod\ \ \ 1000000007(10^9 + 7) $的结果。

Solution

\[\begin{align*} &\sum_{i=1}^n\sum_{j=1}^n \sigma(ij)\\ =&\sum_{i=1}^n\sum_{j=1}^n\sum_{p|i}\sum_{q|j}\frac{iq}p[gcd(p,q)=1]\\ =&\sum_{d=1}^n\mu(d)\sum_{i=1}^n\sum_{j=1}^n\sum_{p|i}\sum_{q|j}\frac{iq}p[d|gcd(p,q)]\\ =&\sum_{d=1}^n\mu(d)\sum_{i=1}^n\sum_{j=1}^n\sum_{dp|i}\sum_{dq|j}\frac{iq}p\\ =&\sum_{d=1}^nd\mu(d)\sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac nd}\sum_{p|i}\sum_{q|j}\frac{iq}p\\ =&\sum_{d=1}^nd\mu(d)(\sum_{i=1}^{\frac nd}\sum_{p|i}\frac ip)(\sum_{j=1}^{\frac nd}\sum_{q|j}q)\\ =&\sum_{d=1}^nd\mu(d)\sum_{i=1}^{\frac nd}\sigma^2(i) \end{align*} \]

第一个等号：相当于是说干掉 \(i\) 的一部分后，补上 \(j\) 的一部分。为了防止算重，也就是 \(\frac i{pa}qa=\frac ip q\) 这样两种情况是一样的但是算了两遍，我们要求 \(p,q\) 互质

第二个等号：我们知道莫反是 \(\sum_{d|n}\mu(d)=[n=1]\) 。在此处，只有当 \(d|gcd(p,q)\) 的时候才会使当前枚举的这个 \(\mu(d)\) 产生效果，即 \(\sum_{d=1}^n\mu(d)[d|n]=\sum_{d|n}\mu(d)\)

第三个等号：为了直接满足 \([d|gcd(p,q)]\) 的条件，我们直接枚举 \(dp,dq\)

第四个等号：发现需要满足 \(d|i,d|j\) ，不妨直接枚举 \(i,j,p,q\) 包含了多少个 \(d\) ，但是这样实际上算的应该是 \(\dots \sum_{q|j}\frac{(id)(qd)}{pd}=\frac{iq}p d\) ，这里把 \(d\) 提到了前面

第五个等号：简单地对式子换了一下顺序并分组

第六个等号：显然 \(\sum_{p|i}p\) 代表着 \(\sigma(i)\)

至此 \(\sum_{i=1}^nd\mu(d)\) 显然可以用杜教筛解决，令 \(g=id\) 即可

对于 \(\sum_{i=1}^n\sigma(i)\) 的计算，我们可以考虑枚举对于每一个 \(i\leq n\) ，在 \(1\dots n\) 中有多少个数是它的倍数：

\[\sum_{i=1}^n \sigma(i)=\sum_{i=1}^n i\lfloor \frac ni\rfloor \]

即有 \(\lfloor \frac ni \rfloor\) 个数是 \(i\) 的倍数 ， \(i\) 造成了这么多次贡献

显然，这部分可以使用整除分块解决。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e6+5;
const int mod = 1e9+7;
const int inv2 = 500000004;

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
    int s=0,w=1; char ch=getchar();  
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}

int prime[N],mu[N];
int n,cnt,ans;
map<int,int>ansm;
bool vis[N];

void getprime(int n){
    mu[1]=1;
    for(int i=2;i<n;++i){
        if(!vis[i])prime[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&prime[j]*i<n;++j){
            vis[prime[j]*i]=true;
            if(i%prime[j]==0)break;
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<n;++i)
        mu[i]=(i*mu[i]%mod+mu[i-1])%mod;
}
int calcm(int n){
    if(n<N)return mu[n];
    if(ansm[n])return ansm[n];
    int res=1;
    for(int i=2,j;i<=n;i=j+1)j=n/(n/i),
        res=(res-(j-i+1)%mod*(i+j)%mod*inv2%mod*calcm(n/i)%mod+mod)%mod;
    return ansm[n]=res;
}
int calcs(int n){
    int res=0;
    for(int i=1,j;i<=n;i=j+1)j=n/(n/i),
        (res+=(j-i+1)%mod*(i+j)%mod*inv2%mod*(n/i)%mod)%=mod;
    return res;
}

signed main(){
    n=read(),getprime(N);
    for(int i=1,j,t;i<=n;i=j+1)
        t=calcs(n/i),j=n/(n/i),
        (ans+=((calcm(j)-calcm(i-1))%mod+mod)%mod*t%mod*t%mod)%=mod;
    printf("%lld\n",ans);
    return 0;
}

这篇关于「51nod1220」 约数之和 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！