求助,为何这种 O(nlogn)的也会超时
查看原帖
求助,为何这种 O(nlogn)的也会超时
672837
DaShabby楼主2023/7/27 10:46
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long ll;
const int maxn = 5e5+23;
ll MOD= 1e9+7;
int a[6000];//,vis[maxn],idx;
vector<int>fac[maxn*2];
void inti(int n){
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j+=i){
//			if(i%j)continue;
			fac[j].push_back(i);
//			if(j!=i/j)fac[i].push_back(i/j);
		}
	}
} 
void work(){
	int n;
	scanf("%d",&n);
	inti(n);
	ll ans=0;
//	for(int i=1;i<=n;i++){
//		ll x=fac[i].size();
//		ans=max(ans,x);
//	
//	}
	for(int i=1;i<=n;i++)ans+=fac[i].size();
	printf("%lld\n",ans);
}

int main()
{
//	inti();
    int t=1;
//    scanf("%d",&t);
	while(t--)
	work();
	
    return 0;
}
2023/7/27 10:46
加载中...