题目链接：

http://www.51nod.com/Challenge/Problem.html#!#problemId=1237
我们想要求所有的 $gcd(i,j)$gcd(i,j)的和，换一个思路就是看 $gcd(i,j)=d$gcd(i,j)=d对答案的贡献，（感觉好多题都是换一种思路来看对答案的贡献的），那如果能够快速求出 $gcd(i,j)=d$gcd(i,j)=d的有几个就好了
假如说 $gcd(i,j)=d$gcd(i,j)=d的有 $cnt\left(d\right)$cnt(d)个，那么 $ans=\sum _{d=1}^{n}d\cdot cnt\left(d\right)$ans=d=1∑n​d⋅cnt(d)

那么现在结论就是：
$cnt\left(d\right)=2\cdot S\left(\frac{n}{d}\right)-1$cnt(d)=2⋅S(dn​)−1
其中S(n)表示欧拉函数前缀和：
$S\left(n\right)=\sum _{i=1}^n\phi \left(i\right)$S(n)=i=1∑n​φ(i)

那么为什么喃？
先来看这个：
$\sum _{i=1}^n\sum _{j=1}^n\left[gcd\right(i,j)==1]=2\sum _{i=1}^n\sum _{j=1}^{i-1}\left[gcd\right(i,j)==1]+1$i=1∑n​j=1∑n​[gcd(i,j)==1]=2i=1∑n​j=1∑i−1​[gcd(i,j)==1]+1
这个还是很好理解的，因为 $gcd(i,j)$gcd(i,j)和 $gcd(j,i)$gcd(j,i)是对称的，主对角线分成两半就行

加1是因为 $gcd(1,1)=1$gcd(1,1)=1
然后再修改一哈，把 $gcd(1,1)$gcd(1,1)加进去， $j$j从 $1$1到 $i$i而不是 $i-1$i−1了
$\sum _{i=1}^n\sum _{j=1}^n\left[gcd\right(i,j)==1]=2\sum _{i=1}^n\sum _{j=1}^i\left[gcd\right(i,j)==1]-1$i=1∑n​j=1∑n​[gcd(i,j)==1]=2i=1∑n​j=1∑i​[gcd(i,j)==1]−1
有了这个之后，来看里面那层求和，其实这层求和就是欧拉函数的定义，所以
$\sum _{j=1}^i\left[gcd\right(i,j)==1]=\phi \left(i\right)$j=1∑i​[gcd(i,j)==1]=φ(i)

所以： $\sum _{i=1}^n\sum _{j=1}^n\left[gcd\right(i,j)==1]=2\sum _{i=1}^n\phi \left(i\right)-1$i=1∑n​j=1∑n​[gcd(i,j)==1]=2i=1∑n​φ(i)−1
所以：
$\sum _{i=1}^n\sum _{j=1}^n\left[gcd\right(i,j)==1]=2S\left(n\right)-1$i=1∑n​j=1∑n​[gcd(i,j)==1]=2S(n)−1

那现在要找 $gcd(i,j)=d$gcd(i,j)=d的个数就是求 ${\sum }_{i=1}^n{\sum }_{j=1}^n\left[gcd\right(i,j)==d]$∑i=1n​∑j=1n​[gcd(i,j)==d]

因为如果： $gcd(i,j)==d$gcd(i,j)==d，那么 $gcd(\frac{i}{d},\frac{j}{d})=1$gcd(di​,dj​)=1
所以就有：
$\sum _{i=1}^n\sum _{j=1}^n\left[gcd\right(i,j)==d]=\sum _{i=1}^{\frac{n}{d}}\sum _{j=1}^{\frac{n}{d}}\left[gcd\right(i,j)==1]=2\cdot S\left(\frac{n}{d}\right)-1$i=1∑n​j=1∑n​[gcd(i,j)==d]=i=1∑dn​​j=1∑dn​​[gcd(i,j)==1]=2⋅S(dn​)−1

好有了公式 $ans=\sum _{d=1}^{n}d\cdot (2\cdot S(\frac{n}{d})-1)$ans=d=1∑n​d⋅(2⋅S(dn​)−1)之后，貌似 $d$d还是要从1遍历到n，还是至少都是线性复杂度啊

这里就用到了整除分块了， $\frac{n}{d}$dn​不变的这段区间，虽然 $d$d会变，但是是公差为1的等差数列，所以这一段的d也能一口气计算，所以整个复杂度就低了

#include"bits/stdc++.h"
using namespace std;
const int maxn=1e6+5;
typedef long long LL;
const LL MOD=1e9+7;
const LL inv2=5e8+4;
bool vis[maxn];
LL phi[maxn],Sphi[maxn];//欧拉函数,欧拉函数前缀和 
vector<int>prime;
map<LL,LL>Mp;
void PHI(int n)
{
	memset(vis,1,sizeof(vis));
	phi[1]=1;
	Sphi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(vis[i])
		{
			prime.push_back(i);
			phi[i]=i-1;
		}
		for(int j=0;j<prime.size()&&i*prime[j]<=n;j++)
		{
			vis[i*prime[j]]=0;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
		Sphi[i]=(Sphi[i-1]+phi[i])%MOD;
	}
}
LL S(LL n)//计算欧拉函数前缀和 
{
	if(n<=maxn-5)return Sphi[n];
	if(Mp[n])return Mp[n];
	LL res=(n%MOD)*((n+1)%MOD)%MOD*inv2%MOD;
	for(LL i=2,j;i<=n;i=j+1)
	{
		j=n/(n/i);
		res-=(LL)(j-i+1)%MOD*S(n/i)%MOD;
		res%=MOD;
	}
	res=(res+MOD)%MOD;
	return Mp[n]=res;
}
LL calc(LL i,LL j)//计算从i到j的公差为1的等差数列的和 
{
	LL res=(i+j)%MOD*(j-i+1LL)%MOD*inv2%MOD;
	return res%MOD;
 } 
int main()
{
	PHI(maxn-5);
	LL N;
	while(cin>>N)
	{
		LL res=0;
		for(LL d=1,j;d<=N;d=j+1)
		{
			j=N/(N/d);
			res+=calc(d,j)*(2LL*S(N/d)-1)%MOD;
			res%=MOD;
		}
		res=(res+MOD)%MOD;
		cout<<res<<endl;
	}
}