90分求助
  • 板块P2398 GCD SUM
  • 楼主fyc_LC
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/11/19 20:58
  • 上次更新2024/11/19 22:18:15
查看原帖
90分求助
1059675
fyc_LC楼主2024/11/19 20:58
#include<bits/stdc++.h>
using namespace std;
bool np[10006000];
long long p[10006000];
long long phi[10006000];//phi
long long sum[10006000];
int main(){
	p[1]=1;
	phi[1]=1;
	long long n;
	cin>>n;
	long long cnt=2;
	for(long long i=2;i<n;i++){
		if(np[i]==0){
			p[cnt++]=i;
			phi[i]=i-1;
		}
		for(long long j=2;j<=cnt&&p[j]*i<=n;j++){
			np[p[j]*i]=1;
			if(i%p[j]==0){
				phi[p[j]*i]=phi[i]*p[j];
				break;
			}
			phi[p[j]*i]=phi[p[j]]*phi[i];
			
		}
	}
	unsigned long long ans=0;
	for(long long i=1;i<=n;i++){
		sum[i]=sum[i-1]+phi[i];
	}
	for(long long i=1;i<=n;i++){
		ans+=(sum[n/i]*2-1)*i;
	}
	cout<<ans;
	return 0;
}

输入2663应输出35716800 但却输出35711476

2024/11/19 20:58
加载中...