Discription
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)的结果。
Input
输入一个数N(2 <= N <= 10^9)。
Output
输出S(N) Mod 1000000007(10^9 + 7)的结果。
Input示例
1000
Output示例
576513341
我们知道的是，当d(x)表示x的约数的时候，d(i*j)=Σ(p|i)Σ(q|j) [gcd(p,q)==1]
但是当d(x)表示x的约数之和的时候，d(i*j)=Σ(p|i)Σ(q|j) p*q [gcd(p,j/q)==1]
这两者都可以通过质因子分解来证明。
然后式子就好推了，我这里就不推了23333
#include<bits/stdc++.h>
#define ll long long
#define ha 1000000000
using namespace std;
const int maxn=10000000;
ll zs[maxn/5],miu[maxn+5];
ll t=0,low[maxn+5];
bool v[maxn+5];
ll d[maxn+5];
map<ll,ll> mmpd;
map<ll,ll> mmpmiu;
ll n;
inline ll add(ll x,ll y){
x+=y;
return x>=ha?x-ha:x;
}
inline ll c(ll x){
if(x>ha) x%=ha;
return (x*(x+1)>>1)%ha;
}
inline void init(){
d[1]=1,low[1]=1,miu[1]=1;
for(int i=2;i<=maxn;i++){
if(!v[i]) zs[++t]=i,miu[i]=-1,d[i]=i+1,low[i]=i;
for(int j=1,u;j<=t&&(u=zs[j]*i)<=maxn;j++){
v[u]=1;
if(!(i%zs[j])){
low[u]=low[i]*zs[j];
if(low[i]==i) d[u]=d[i]*zs[j]+1ll;
else d[u]=d[low[u]]*d[i/low[i]];
break;
}
low[u]=zs[j];
miu[u]=-miu[i];
d[u]=d[i]*(zs[j]+1);
}
}
for(int i=1;i<=maxn;i++){
d[i]=add(d[i-1],d[i]);
miu[i]=add(add(miu[i]*i,ha),miu[i-1]);
}
}
inline ll getmiu(ll x){
if(x<=maxn) return miu[x];
if(mmpmiu.count(x)) return mmpmiu[x];
ll an=ha-1;
for(ll i=2,j,now;i<=x;i=j+1){
now=x/i,j=x/now;
an=add(an,add(c(j),ha-c(i-1))*(ll)getmiu(now)%ha);
}
an=ha-an;
mmpmiu[x]=an;
return an;
}
inline ll getd(ll x){
if(x<=maxn) return d[x];
if(mmpd.count(x)) return mmpd[x];
ll an=0;
for(ll i=1,j,now;i<=x;i=j+1){
now=x/i,j=x/now;
an=add(an,add(c(j),ha-c(i-1))*(now%ha)%ha);
}
mmpd[x]=an;
return an;
}
inline void solve(){
ll pre=0,an=0,oops,val;
for(ll i=1,j,now;i<=n;i=j+1){
now=n/i,j=n/now,oops=getmiu(j);
val=getd(now),val=val*(ll)val%ha;
an=add(an,add(oops,ha-pre)*(ll)val%ha);
pre=oops;
}
printf("%lld
",an);
}
int main(){
init();
scanf("%lld",&n);
solve();
return 0;
}