2020牛客寒假算法基础集训营6 题解

迟到了整整一年的题解... 想想当时真的菜... ## E-立方数 ### 题目大意 共 $T$ 组数据，对于每组数据，给定的正整数 $N$，求最大的正整数 $A$，使得存在正整数 $B$，满足 $A^3B=N$，其中 $T\le 10^5, N\le10^{18}$ ### 思路 经过简单的分析，可以想到 $A$ 一定小于 $\sqrt[3] N=10^6$，因此线性筛预处理出 $10^6$ 内的质数试除即可，复杂度 $O(T\frac {\sqrt[3]N}{\ln{\sqrt[3]N}})$，（质数个数 $Li(x)={x\over \ln x}$），这样复杂度还是不能满足题目，只能通过 $60\%$ 的测试数据。 我们发现，如果将 $\sqrt[4]N$ 内的质数全部筛去，剩下要么是个完全立方数，要么就直接是 $B$，我们可以二分判断剩下的这个数是否为完全立方数，如果是就计入答案，不是则直接输出前面筛出来的答案。 ### code ``` cpp #include <algorithm> #include <cstdio> using namespace std; const int maxn = 31625; int t, pr[maxn], prime[maxn], top = 0; long long n, l = 1, r = 1e6; inline void getPrime(int maxprime) { pr[1] = 1; for (int i = 2; i <= maxprime; ++i) { if (!pr[i]) prime[++top] = i; for (int j = 1; j <= top && i * prime[j] <= maxprime; ++j) { pr[i * prime[j]] = 1; if (!(i % prime[j])) break; } } } int main() { getPrime(maxn - 2); for (scanf("%d", &t); t--; l = 1, r = 1e6) { long long ans = 1; scanf("%lld", &n); for (int i = 1, now = 0; i <= top; ++i, now = 0) { while (!(n % prime[i])) { ++now, n /= prime[i]; if (now >= 3) now -= 3, ans *= prime[i]; } } if (n == 1) { printf("%lld\n", ans); continue; } while (l < r) { long long mid = l + r >> 1; (mid * mid * mid < n) ? l = mid + 1 : r = mid; } printf("%lld\n", ans * (l * l * l == n ? l : 1)); } return 0; } ``` ## E-立方数 ### 题意