60pts,但是剩下四个WA
查看原帖
60pts,但是剩下四个WA
1085667
KohaD_SEGA楼主2024/1/28 22:15
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1000000007;
ll Mu[10000001];
ll Prime[2000000];
ll vis[10000001];
void CalMu(ll n)
{
	Mu[1]=1;
	ll tot=0;
	for(ll i=2;i<=n;i++)
	{
		if(!vis[i])
		{
			Prime[++tot]=i;
			Mu[i]=-1;
		}
		for(ll j=1;j<=tot && i*Prime[j]<=n;j++)
		{
			vis[i*Prime[j]]=1;
			if(i%Prime[j]==0)	break;
			Mu[i*Prime[j]]=-Mu[i];
		}
	}
	for(ll i=2;i<=n;i++)	Mu[i]+=Mu[i-1];
}
inline ll solve(ll m)
{
	ll ans=0;
	for(ll l=1,r;l<=m;l=r+1)
	{
		r=m/(m/l);
		ans+=(Mu[r]-Mu[l-1])*(m/l)*(m/l);
		ans=(ans%MOD+MOD)%MOD;
	}
	return (ans%MOD+MOD)%MOD;
}
inline ll sq(ll x)
{
	ll re=(2*x+1)*(x+1)*x/6;
	return (re%MOD+MOD)%MOD;
}
int main()
{
	ll n;
	cin>>n;
	CalMu(n);
	ll ans=0;
	for(ll l=1,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		ans+=(sq(r)-sq(l-1))*solve(n/l);
		ans=(ans%MOD+MOD)%MOD;
	}
	cout<<ans<<endl;	
}

sq(x)=∑n⩽xn2sq(x)=\sum\limits_{n\leqslant x} n^2

2024/1/28 22:15
加载中...