题目
题目描述
对于给定的正整数 N，求最大的正整数 A，使得存在正整数 B，满足 \(A^3B=N\)
输入包含 T 组数据，1≤T≤10,000；\(1≤N≤10^{18}\)
输入描述
第一行数字 T 表示数据组数
接下来一行，T 个正整数 N
输出描述
T 行，每行一个数字表示答案
示例1
输入
4
27 24 7 54
输出
3
2
1
3
题解
知识点：分解质因数，枚举。
直接枚举 \(A\) 的复杂度是 \(O(\sqrt[3]{n})\) ，但有 \(10^4\) 组数据，所以是不行的。
考虑对 \(N\) 分解质因数，从小到大枚举质因数，将幂次大于 \(3\) 的质因数的幂次给 \(A\) 即可。直到幂次小于等于 \(3\) ，此时要么剩下唯一一个质因子的 \(3\) 次方，要么都不足 \(3\) 次方，特判即可。
此时，还需要预处理 \(O(\sqrt[4] n)\) 内的素数，因为单纯枚举质因子还是会超时。
时间复杂度 \(O \left( T \cdot \dfrac{\sqrt[4]n}{\log n} \right)\)
空间复杂度 \(O(\sqrt[4]n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 31622;// 10^(18/4)，质因子幂次小于等于3时可以直接特判
bool vis[N];
vector<int> prime;
void get_prime(int n) {
for (int i = 2;i <= n;i++) {
if (!vis[i]) prime.push_back(i);
for (auto j : prime) {
if (i * j > n) continue;
vis[i * j] = 1;
if (!(i % j)) break;
}
}
}
ll get_pfactor(ll n) {
ll ans = 1;
for (auto i : prime) {
if (i * i * i * i > n) break;
int cnt = 0;
while (!(n % i)) n /= i, cnt++;
for (int j = 3;j <= cnt;j += 3) ans *= i;
}
ll t = pow(n, 1.0 / 3);
if (n == t * t * t) ans *= t;
else if (n == (t + 1) * (t + 1) * (t + 1)) ans *= t + 1;
return ans;
}
bool solve() {
ll n;
cin >> n;
cout << get_pfactor(n) << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
get_prime(N);
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}