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

2021-01-22 13:22:48


迟到了整整一年的题解...
想想当时真的菜...

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

#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-立方数

题意