60pts分解质因数超时 求调
查看原帖
60pts分解质因数超时 求调
1244840
Fatsheep_110922楼主2024/7/27 00:44
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll, int>mp;
inline ll fastpow(ll a, int b)
{
	if(b == 0) return 1;
	if(b == 1) return a;
	ll tmp = fastpow(a, b/2);
	if(b % 2) return tmp*tmp*a;
	return tmp*tmp;
}
inline ll easy(ll x) // 化简根式
{
	mp.clear();
	ll tmp = x;
	for(ll i = 2;i <= x/i;++i)
	{
		while(tmp % i == 0)
		{
			tmp /= i;
			mp[i]++;
		}
		if(tmp == 1) break;
	}
	if(tmp > 1) mp[tmp]++;
	ll ans = 1;
	for(auto i : mp) ans *= fastpow(i.first, i.second/3);
	return ans;
}
int main()
{
	int n;
	ll x;
	scanf("%d", &n);
	while(n--)
	{
		scanf("%lld", &x);
		printf("%lld\n", easy(x));
	}
	return 0;
}

2024/7/27 00:44
加载中...