[51nod1220] 约数之和（杜教筛+莫比乌斯反演）

题面

传送门

题解

嗯……还是懒得写了……这里

//minamoto

#include<bits/stdc++.h>

#define R register

#define IT map<int,int>::iterator

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

using namespace std;

const int N=1e6+5,P=1e9+7,inv2=500000004;

bitset<N>vis;int p[N],mu[N],f[N],g[N],m,sqr,n;map<int,int>mp;

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

inline int calc(R int x){return (1ll*x*(x+1)>>1)%P;}

void init(int n){

	f[1]=1;

	fp(i,2,n){

		if(!vis[i])p[++m]=i,mu[i]=P-1;

		for(R int j=1;j<=m&&1ll*i*p[j]<=n;++j){

			vis[i*p[j]]=1;

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

			mu[i*p[j]]=P-mu[i];

		}

	}

	fp(i,2,n)f[i]=add(f[i-1],mul(mu[i],i));

	fp(i,1,n)for(R int j=i;j<=n;j+=i)g[j]=add(g[j],i);

	fp(i,2,n)g[i]=add(g[i-1],g[i]);

}

int F(int n){

	if(n<=sqr)return f[n];

	IT it=mp.find(n);

	if(it!=mp.end())return it->second;

	int res=1,las=1,now;

	for(int i=2,j;i<=n;i=j+1)

		j=n/(n/i),now=calc(j),res=dec(res,mul(now-las+P,F(n/i))),las=now;

	return mp[n]=res;

}

int G(int n){

	if(n<=sqr)return g[n];

	int res=0,las=0,now;

	for(R int i=1,j;i<=n;i=j+1)

		j=n/(n/i),now=calc(j),res=add(res,mul(now-las+P,n/i)),las=now;

	return res;

}

int main(){

//	freopen("testdata.in","r",stdin);

	scanf("%d",&n),init(sqr=N-5);

	int res=0,las=0,now,x;

	for(R int i=1,j;i<=n;i=j+1)

		j=n/(n/i),now=F(j),x=G(n/i),res=add(res,mul(now-las+P,mul(x,x))),las=now;

	printf("%d\n",res);

	return 0;

}