/onlineJudge/questionCode.html#!problemId=2026
参考及推导：/ivorysi/p/9157781.html
（其公式有一处小问题，请注意。）
然后就没了……我觉得讲得挺详细了。
另外map跑得可能比哈希表还快可还行。
#include<map>#include<cmath>#include<stack>#include<queue>#include<cstdio>#include<cctype>#include<vector>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long ll;const int p=1e9+7;const int N=31623;const int M=2e6+5;const int MOD=9747111;const int INV=500000004;inline int read(){int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X;}struct node{int to,nxt,w;}e[M];bool he[N+5];int su[N+5],tot,cnt,head[MOD+5],mu[N+5],sum[N+5];inline void add(int v,int w){int u=v%MOD;e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;}inline int query(int v){int u=v%MOD;for(int i=head[u];i;i=e[i].nxt)if(v==e[i].to)return e[i].w;return -1;}inline int sub(int a,int b){a-=b;if(a<0)a+=p;if(a>=p)a-=p;return a;}inline int inc(int a,int b){a+=b;if(a<0)a+=p;if(a>=p)a-=p;return a;}inline int AP(int l,int r){return (ll)inc(l,r)*sub(r+1,l)%p*INV%p;}void Euler(int n){mu[1]=1;for(int i=2;i<=n;i++){if(!he[i]){su[++tot]=i;mu[i]=-1;}for(int j=1;j<=tot&&i*su[j]<=n;j++){int pri=su[j];he[i*pri]=1;if(i%pri==0){mu[i*pri]=0;break;}else mu[i*pri]=mu[i]*mu[pri];}}for(int i=1;i<=n;i++)sum[i]=inc(sum[i-1],mu[i]*i);}int S(int n){if(n<=N)return sum[n];int tmp=query(n);if(tmp!=-1)return tmp;int ans=0;for(int i=2,j;i<=n;i=j+1){j=n/(n/i);ans=inc(ans,(ll)AP(i,j)*S(n/i)%p);}ans=sub(1,ans);add(n,ans);return ans;}int main(){Euler(N);int n=read(),ans=0;for(int i=1,j;i<=n;i=j+1){j=n/(n/i);ans=inc(ans,(ll)sub(S(j),S(i-1))*(n/i)%p);}printf("%lld\n",(ll)ans*ans%p);return 0;}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
