85pts 求调
查看原帖
85pts 求调
555065
ChrysanthBlossom楼主2024/4/5 22:48

你给个多少分都好啊,让我 WA 掉第一个 subtask 是什么意思

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define ld long double
using namespace std;
const int maxn=2e7+7;
int n;
bool np[maxn];
int phi[maxn];
vector<int>pri;
int sum[maxn];
void init(int limit){
	phi[1]=1;
	for(ri i=2;i<=limit;i++){
		if(!np[i]){
			pri.emplace_back(i);
			phi[i]=i-1;
		}
		for(int p:pri){
			if(i*p>limit)break;
			np[i*p]=1;
			if(i%p==0){
				phi[i*p]=phi[i]*p;
				break;
			}
			else phi[i*p]=phi[i]*phi[p];
		}
	}
	for(ri i=1;i<=limit;i++){
		sum[i]=sum[i-1]+int(log(i)/log(10)+1);
	}
}
bool vis[5003][5003];
void solve(){
	ld ans=0;
	for(ri a=1;a<=n;a++){
		for(ri b=1;b<=a;b++){
			if(!vis[a][b]){
				int len=log(a)/log(10)+1;
				ans+=len*log(len)/log(2);
				for(ri i=1;a*i<=n;i++){
					if(vis[a*i][b*i])continue;
					vis[a*i][b*i]=1;
					ans+=int(log(i)/log(10)+1);
				}
			}
		}
	}
	cout<<fixed<<setprecision(9)<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	if(n<=5000)solve();
	init(n);
//	for(ri i=1;i<=n;i++){
//		cout<<phi[i]<<' ';
//	}
//	cout<<endl;
//	for(ri i=1;i<=n;i++){
//		cout<<log(i)+1<<' ';
//	}cout<<endl;
	ld ans=0;
	for(ri i=1;i<=n;i++){
		int len=log(i)/log(10)+1;
		ans+=phi[i]*(len*log(len)/log(2)+sum[n/i]);
	}
	cout<<fixed<<setprecision(9)<<ans<<endl;
	return 0;
}
2024/4/5 22:48
加载中...