ABC-D 4TLE8WA求调
  • 板块学术版
  • 楼主T20201126
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/12/3 21:59
  • 上次更新2023/10/27 00:34:07
查看原帖
ABC-D 4TLE8WA求调
419474
T20201126楼主2022/12/3 21:59
#include<bits/stdc++.h>
using namespace std;
long long p[1000007],q[1000007];
long long ss[1000007],w[1000007];
long long k,cnt,now,dai;
long long num,maxx;
bool ssp(long long x){
	if(x<2) return false;
	for(int i=2;i*i<=x;++i)
	if(x%i==0) return false;
	return true;
} 

signed main(){
	scanf("%lld",&k);
	if(ssp(k)) {
		cout<<k;
		return 0;
	}
	for(int i=2;i<=1000006;++i)
	{
		if(!p[i])
			ss[++cnt]=i;
		for(int j=1;ss[j]*i<=1000007;++j)
		{
			p[ss[j]*i]=1;
			if(i%ss[j]==0) break;
		}
	}
	
	for(int i=1;i<=cnt;++i)
	{
		if(k%ss[i]==0) w[++num]=i;
		while(k%ss[i]==0){
			++q[i];
			k/=ss[i];
		}
	}
	maxx=k;
	for(int i=1;i<=num;++i)
	{
		now=1;int j=1;
		while(now<q[w[i]])
		{
			++now;dai=j;
			while(dai%ss[w[i]]==0){
				++now;
				dai/=ss[w[i]];
			}
			++j;
		}
		//cout<<j*ss[w[i]]<<endl;
		maxx=max(maxx,j*ss[w[i]]);
	}
	cout<<maxx;
	return 0;
}
2022/12/3 21:59
加载中...