过样例光速全WA求助
查看原帖
过样例光速全WA求助
756660
B612Dusk楼主2024/7/19 13:32

rt,飞快的全Wa求助

#include <bits/stdc++.h>
#define pb push_back
#define int long long

//const int N = ;

inline int read()
{
	int t;
	scanf("%lld", &t);
	return t;
}

int n, ans;
std::vector<int> vec;
std::map<int, int> mp;

void dfs(int x)
{
	int now2 = 1;
	while(now2 <= x)
	{
		vec.pb(now2);
		int now3 = now2;
		while(now3 <= x)
		{
			now3 *= 5;
			if(now3 <= x)	vec.pb(now3);
		}
		now2 <<= 1;
	}
}

inline int find(int x, bool op)
{
	int l = 0, r = vec.size();
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(vec[mid] >= x)	 r = mid - 1;
		else	l = mid + 1;
	}
	if(vec[l] > x && op)	-- l;
	return l;
}

signed main()
{
	n = read();
	
	dfs(n);
	sort(vec.begin(), vec.end());
	
	for(int i = 0;i < vec.size();i = -~i)
		printf("%lld ", vec[i]);
	
	for(int l = 1, r; l <= n;l = r + 1)
	{
		r = n / (n / l);
		ans += (r - l + 1) * (n / l);
				
		// ------------ 处理了整除 
		
		int L = find(l, 0), R = find(r, 1);
		
		ans -= (R - L + 1) * (n / l);
		ans += (R - L + 1) * n;
	}	
	
	printf("%lld\n", ans);
	return 0; 
}
/*===========================================
problem : ZAP
author : B612Dusk
time : 2024.7.19
start : 13:08
finish : 13:31
============================================*/
2024/7/19 13:32
加载中...