【51nod1220】约数之和

题目

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

定义S(N) = ∑1<=i<=N ∑1<=j<=N d(i*j)。

例如：S(3) = d(1) + d(2) + d(3) + d(2) + d(4) + d(6) + d(3) + d(6) + d(9) = 59，S(1000) = 563576517282。

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

分析

分开处理每个质因子，于是\(d(i*j)=\sum_{p|i}\sum_{q|j}\dfrac{iq}{p}[gcd(p,q)=1]\)

\[ans=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{p|i}\sum_{q|j}\dfrac{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}\dfrac{iq}{p}[d|gcd(p,q)]
\]

\[=\sum_{d=1}^{n}\mu(d)\sum_{p|i}\sum_{q[j}\dfrac{q}{p}\sum_{p[i}i\sum_{q[j}
\]

\[=\sum_{d=1}^{n}\mu(d)\sum_{p|i}\sum_{q[j}\dfrac{q}{p}{\lfloor\dfrac{n}{q}\rfloor}{p\dfrac{\lfloor\dfrac{n}{p}\rfloor(\lfloor\dfrac{n}{p}\rfloor+1)}{2}}
\]

\[=\sum_{d=1}^{n}\mu(d)d(\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}q{\lfloor\dfrac{n}{dq}\rfloor})(\sum_{q=1}^{\lfloor\frac{n}{d}\rfloor}{\dfrac{\lfloor\dfrac{n}{dp}\rfloor(\lfloor\dfrac{n}{dp}\rfloor+1)}{2}})
\]

考虑处理\(\sum_{q=1}^{\lfloor\frac{n}{d}\rfloor}{\dfrac{\lfloor\dfrac{n}{dp}\rfloor(\lfloor\dfrac{n}{dp}\rfloor+1)}{2}}\)

用\(n\)代替\(\lfloor\dfrac{n}{d}\rfloor\)

即

\[\sum_{i=1}^{n}{\dfrac{\lfloor\dfrac{n}{i}\rfloor(\lfloor\dfrac{n}{i}\rfloor+1)}{2}}
\]

\[=\sum_{i=1}^{n}\sum_{j=1}^{\lfloor\dfrac{n}{i}\rfloor}j
\]

\[=\sum_{j=1}^{n}j\sum_{i=1}^{\lfloor\dfrac{n}{j}\rfloor}
\]

\[=\sum_{j=1}^{n}j\lfloor\dfrac{n}{j}\rfloor(事实上，这就等于\sum_{j=1}^{n}d(j))
\]

\[ans=\sum_{d=1}^{n}\mu(d)d(\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}q{\lfloor\dfrac{n}{dq}\rfloor})^2
\]

于是对于两层\(\sum\)都分块处理

类似与【51nod 2026】Gcd and Lcm，可以用杜教筛处理\(\mu(d)d\)的前缀和。

对于\(\sum_{j=1}^{n}j\lfloor\dfrac{n}{j}\rfloor\)，直接上分块。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

#include <map>

const int maxlongint=2147483647;

const long long mo=1e9+7;

const int lim=1e5+7;

const int N=10000005;

using namespace std;

#define sqr(x) (1ll*(x)*(x)%mo)

#define val(x,y) (1ll*(y-x+1)*(x+y)/2%mo)

int p[N],mu[N],n,ha[lim+5][2],s[N],ans;

bool bz[N];

int get(int v)

{

	int x;

	for(x=v%lim;ha[x][0] && ha[x][0]!=v;(++x)-=x>=lim?lim:0);

	return x;

}

int S(int m)

{

	if(m<=N-5) return s[m];

	int pos=get(m);

	if(ha[pos][0]) return ha[pos][1];

	ha[pos][0]=m;

	int la=0,sum=0;

	for(int i=2;i<=m;i=la+1)

	{

		la=m/(m/i);

		sum=(1ll*sum+1ll*val(i,la)*S(m/i))%mo;

	}

	return ha[pos][1]=(1-sum+mo)%mo;

}

int main()

{

	scanf("%d",&n);

	mu[1]=s[1]=1;

	for(int i=2;i<=N-5;i++)

	{

		if(!bz[i]) mu[p[++p[0]]=i]=-1;

		s[i]=(s[i-1]+mu[i]*i+mo)%mo;

		for(int j=1,k;j<=p[0] && (k=i*p[j])<=N-5;j++)

		{

			bz[k]=true;

			if(i%p[j]==0) break;

			mu[k]=-mu[i];

		}

	}

	int la=1;

	for(int i=1;i<=n;i=la+1)

	{

		la=n/(n/i);

		int last=1,nn=n/i,sum=0;

		for(int j=1;j<=nn;j=last+1)

		{

			last=nn/(nn/j);

			sum=(1ll*sum+1ll*(val(j,last))*(nn/j))%mo;

		}

		ans=(1ll*ans+1ll*(S(la)-S(i-1)+mo)*sqr(sum))%mo;

	}

	printf("%d",ans);

}

巴特西

【51nod1220】约数之和

题目

分析

最新文章

热门文章