#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long int64;
const int mod=;
#define maxn 2000005
int top,tot,d[maxn],prim[maxn],mu[maxn];
bool vis[maxn];
int64 n,f[maxn],ans;
void prepare(){
tot=top=,memset(vis,,sizeof(vis)),mu[]=,mu[]=,f[]=;
for (int i=;i<maxn;i++){
if (vis[i]==){
prim[++top]=i;
d[i]=i;
mu[i]=-;
f[i]=;
}
for (int j=;j<=top;j++){
if (i*prim[j]>=maxn) break;
vis[i*prim[j]]=;
if (i%prim[j]==){
d[i*prim[j]]=d[i]*prim[j];
mu[i*prim[j]]=;
f[i*prim[j]]=f[i/d[i]]*(f[d[i]]+);
break;
}else{
d[i*prim[j]]=prim[j];
mu[i*prim[j]]=mu[i]*mu[prim[j]];
f[i*prim[j]]=f[i]*f[prim[j]];
}
}
}
for (int i=;i<maxn;i++) mu[i]+=mu[i-];
for (int i=;i<maxn;i++) f[i]=(f[i-]+f[i])%mod;
}
#define maxp 100007
#define maxm 4000005
int now[maxp],prep[maxm];
int64 val[maxm],id[maxm];
void insert(int x,int64 y){
int pos=x%maxp;
prep[++tot]=now[pos],now[pos]=tot,val[tot]=y,id[tot]=x;
}
int64 find(int x){
int pos=x%maxp;
for (int i=now[pos];i;i=prep[i]){
if (id[i]==x) return val[i];
}
return -;
}
int64 Mu(int x){
if (x<maxn) return mu[x];
int64 temp=find(x),t;
if (temp!=-) return temp;
temp=;
for (int j,i=;i<=x;i=j+){
j=x/(x/i); t=Mu(x/i);
temp=((temp-1LL*(j-i+)*t%mod)%mod+mod)%mod;
}
insert(x,temp); return temp;
}
int64 F(int x){
if (x<maxn) return f[x];
int64 temp=;
for (int j,i=;i<=x;i=j+){
j=x/(x/i);
temp=(temp+1LL*(x/i)*(j-i+)%mod)%mod;
}
return temp%mod;
}
int main(){
int64 temp;
prepare();
scanf("%lld",&n);
ans=;
for (int j,i=;i<=n;i=j+){
j=n/(n/i); temp=F(n/i);
ans=(ans+1LL*(Mu(j)-Mu(i-))%mod*temp%mod*temp%mod)%mod;
}
printf("%lld\n",(ans%mod+mod)%mod);
return ;
}
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4176
题目大意：
答案对10^9+7取模。 1<=n<=10^9，单组询问。
吐槽：这是一个对我来说启发很大的题，加深了我对杜教筛的理解。
做法：式子不好写，还是用图好了。
然后用莫比乌斯反演继续化简：
这样就好办了，floor（n/k）最多只有O（sqrt（n））级别的取值，维护mu的前缀和？没错，既然不能预处理，那我们就杜教筛，F数组呢，没错，F[i]=sigam(i/j),1<=j<=i,可以sqrt（n）级别的复杂度做出，如果我们尽可能多的预处理出mu和F，那么可以把总复杂度降至O（n^(2/3)）,足以过此题。