全RE求助
查看原帖
全RE求助
122794
tuya_楼主2020/12/1 20:00
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int n,tot;
#define ll long long
ll pri[maxn],ans,phi[maxn];
int vis[maxn];
int ou(){
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			vis[i]=i;
			phi[i]=i-1;
			pri[++tot]=i;
		}
		for(int j=1;j<=tot;j++){
			if(pri[j]>vis[i]||pri[j]*i>n) break;
			vis[i*pri[j]]=pri[j];
			phi[i*pri[j]]=phi[i]*(i%pri[j]?(pri[j]-1):pri[j]);
		}
	}
}
ll work(int i){
	ll sum=0;
	for(int j=1;j*j<=i;j++)
		if(i%j==0)
			if(i!=j*j) sum+=phi[i/j]*j+phi[j]*(i/j);
			else sum+=phi[i/j]*j;
	return sum;
}
int main(){
	scanf("%d",&n);
    ou();
	for(int i=1;i<=n;i++) ans+=work(i);
	printf("%lld",ans);
	return 0;
}
2020/12/1 20:00
加载中...