最后两点TLE
查看原帖
最后两点TLE
1339889
pjh0625楼主2024/12/13 23:58
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
vector<int> f;
int a[maxn];
void z()
{
	a[1]=1;
	for(int i=2;i<maxn;++i)
	{
		if(!a[i])
		{ 
			f.push_back(i);
			a[i]=i-1; 
		}
		for(int p:f)
		{
			if(i*p>=maxn)
				break;
			a[i*p]=a[i]*(p-1); 
			if(i%p==0)
			{ 
				a[i*p]=a[i]*p;
				break;
			}
		}
	}
}
long long x(int n)
{
	long long sum=0;
	for(int i=1;i<=n;++i)
	{
		sum+=(long long)(a[i])*(n/i)*(n/i);
		sum-=i;
	}
	return sum/2; 
}
int main()
{
	int n;
	cin>>n;
	z();
	long long ans=x(n);
	cout<<ans<<"\n";
	return 0;
}
2024/12/13 23:58
加载中...