【莫比乌斯反演+杜教筛】【51nod 1237】最大公约数之和V3

发布于:2021-07-26 18:18:57

题目

给出一个数N,输出小于等于N的所有数,两两之间的最大公约数之和。


相当于计算这段程序(程序中的gcd(i,j)表示i与j的最大公约数):


由于结果很大,输出Mod 1000000007的结果。


G=0;


for(i=1;i<=N;i++)
{
for(j=1;j<=N;j++)
{
G = (G + gcd(i,j)) % 1000000007;
}
}
N<=1e10


思路

首先我们对柿子进行莫比乌斯反演:

然后我们使用杜教筛把phi(k)筛出来
整除分块做就行


代码

#include
#define ll long long
using namespace std;
const int mod=1e9+7,N=5e6+77;
ll p[N+20],yjy=0,n;
int ph[N+20],cnt,mu[N+20];
bool vis[N+20];
map S;
void init()
{
mu[1]=p[1]=1;
for(int i=2; i<=N; i++)
{
if(!vis[i]) ph[++cnt]=i,mu[i]=-1,p[i]=i-1;
for(int j=1; j<=cnt&&ph[j]*i<=N; j++)
{
vis[ph[j]*i]=1;
if(i%ph[j]==0)
{
p[i*ph[j]]=p[i]*ph[j];
break;
}
p[i*ph[j]]=p[ph[j]]*p[i];
mu[i*ph[j]]=-mu[i];
}
}
for(int i=1; i<=N; i++) mu[i]+=mu[i-1],p[i]+=p[i-1];
}
ll get_phi(ll x)
{
if(x<=N) return p[x];
if(S[x]) return S[x];
ll ans=((1ll+x)*x)/2ll;
for(int l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
ans-=1ll*(r-l+1)*get_phi(x/l);
}
return S[x]=ans;
}
void solve(ll n)
{
for(ll i=1,j; i<=n; i=j+1)
{
j=n/(n/i);
yjy=(yjy+(n/i)*(n/i)%mod*(get_phi(j)-get_phi(i-1))%mod+mod)%mod;
}
}
int main()
{
init();
scanf("%lld",&n);
solve(n);
printf("%lld",yjy);
}









相关推荐

最新更新

猜你喜欢