看心情填坑

这个构造真的太恐怖了。。。果然我还是太年轻。。。

这个问题终于让我把坑填完了。

它解决了我在1222的推导上的主要问题

$\sum_{i=1}^{n}\sum_{j=1}^{n/i}n/i/j*e(gcd(i,j))$

$\sum_{i=1}^{n}n/i*2^{\omega(i)}$

$\omega(i)$表示i的不同质因子个数。

然后发现没法做了，后面的不会算。

这个问题里面提到了$2^{\omega(i)}=\sum_{d|i}(\mu(d))^2$

我这个ZZ觉得真的妙。

然后就可以做了，因为$\sum_{i=1}^{n}(\mu(d))^2=\sum_{i=1}^{\sqrt{n}}n/i^2*\mu(i)$

然后就被卡常了

#include<cstdio>
#include<cmath>
#define size 7000000
#define eps 1e-11
#define size2 15000
#define inf 100000000000000ll
using namespace std;
long long l,r,n;
int cnt;
int mu[size+5],mu2[size+5],d[size+5],last[size+5],prime[500005];
long long smu[size2],smu2[size2],sd[size2];
bool vis[size+5];
inline long long min(long long x,long long y){return x<y?x:y;}
void pre(){
	mu[1]=1;d[1]=1;
	for(int i=2;i<=size;i++){
		if(!vis[i])prime[++cnt]=i,mu[i]=-1,d[i]=2,last[i]=1;
		for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){
			int k=prime[j]*i;
			vis[k]=true;
			if(i%prime[j]==0){mu[k]=0;last[k]=last[i];d[k]=d[i]+d[last[i]];break;}
			else mu[k]=-mu[i],d[k]=d[i]<<1,last[k]=i;
		}
	}
	for(int i=1;i<=size;i++)mu2[i]=mu[i]*mu[i]+mu2[i-1],mu[i]+=mu[i-1],d[i]+=d[i-1];
}
inline long long Smu2(long long k){return k<=size?mu2[k]:smu2[n/k];}
inline long long Smu(long long k){return k<=size?mu[k]:smu[n/k];}
inline long long Sd(long long k){return k<=size?d[k]:sd[n/k];}
inline long long solve(long long p){
	n=p;
	for(int i=n/size;i;i--){
		long long t=n/i;
		smu2[i]=0;
		int tmp=int(sqrt(t)+eps);
		for(int j=1;j<=tmp;j++)smu2[i]+=t/j/j*(mu[j]-mu[j-1]);
		smu[i]=1;
		for(int j=1;j<=tmp;j++){
			smu[i]-=(t/j-t/(j+1))*mu[j];
			if((t/j!=j)&&(j!=1))smu[i]-=Smu(t/j);
		}
		sd[i]=0;
		for(int j=1;j<=tmp;j++){
			sd[i]+=t/j;
			if(t/j!=j)sd[i]+=j*(t/j-t/(j+1));
		}	
	}
	int tmp=int(sqrt(p)+eps);long long ans=0;
	for(int i=1;i<tmp;i++)ans+=(mu2[i]-mu2[i-1])*Sd(p/i)+(Smu2(p/i)-Smu2(p/(i+1)))*d[i];
	if(p/tmp==tmp)ans+=(mu2[tmp]-mu2[tmp-1])*d[tmp];
	else ans+=(mu2[tmp]-mu2[tmp-1])*d[p/tmp]+(mu2[p/tmp]-mu2[p/(tmp+1)])*d[tmp];
	return (ans+p)>>1;	
}
int main(){
	pre();
	scanf("%lld%lld",&l,&r);l--;
	printf("%lld",solve(r)-solve(l));
}