「HDU 6623」Minimal Power of Prime

Description

$T$ 组数据。给定一个正整数 $n$，用质因子乘积的形式表示为 $n = \prod {p_i}^{a_i}$，求 $\min\{ a_i \}$ 。

$(1 \leq T \leq 5 \times 10^4,1 < n \leq 10^{18})$

Source

[hdu]6623

Solution

暴力分解质因数的时间复杂度是 $O(T\sqrt{n})$，显然行不通。

一种巧妙的思路是：我们只提取出 $n​$ 中所有 $\leq \sqrt[5]{n}​$ 的质因子，剩下 $> \sqrt[5]{n}​$ 的质因子最多只有 $4​$ 个，假设它们是 $a,b,c,d​$，分情况讨论，可能是

$$a,a^2,ab,a^3,a^2b,abc,a^4,a^3b,a^2b^2,a^2bc,abcd$$

很容易发现只有 $a^2,a^3,a^4,a^2b^2$ 答案 $> 1$，其余情况不需要考虑（答案一定为 $1$），所以只需要特判是否是 完全平方数/三次方数/四次方数 。不要忘记提前筛出 $\sqrt[5]{n}$ 以内的质数，否则仍然会超时。时间复杂度为 $O(\frac{Tn^\frac{1}{5}}{\log n})$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e4;
int t, tot, prime[MAXN + 5];
LL n;
bool isNotPrime[MAXN + 5];

inline void getPrime(int n) {//线性筛出 10000 以内的质数 
    for (int i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) prime[++tot] = i;
        for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
            isNotPrime[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        } 
    }
}

inline int solve(LL x) {
    //可以用 pow 函数直接开高次根号，但因为精度问题，我们
    //把上取整和下取整的值都验证一下，注意验证时的顺序为从 4 到 2 
    int a = floor(pow(x, 1.0 / 4)), b = ceil(pow(x, 1.0 / 4));
    if (1ll * a * a * a * a == x || 1ll * b * b * b * b == x) return 4;
    a = floor(pow(x, 1.0 / 3)), b = ceil(pow(x, 1.0 / 3));
    if (1ll * a * a * a == x || 1ll * b * b * b == x) return 3;
    a = floor(sqrt(x)), b = ceil(sqrt(x));
    if (1ll * a * a == x || 1ll * b * b == x) return 2;
    return 1;
}

int main() {
    getPrime(MAXN);
    for (read(t); t; --t) {
        read(n);
        int ans = 64;
        for (int j = pow(n, 0.2), i = 1; i <= tot && prime[i] <= j; ++i)
            if (n % prime[i] == 0) {
                int cnt = 0;
                for (; n % prime[i] == 0; n /= prime[i]) ++cnt;
                ans = min(ans, cnt);
            }//提取出 5次根号下 n 的所有质因子 
        if (n > 1) ans = min(ans, solve(n));//若还有多余的质因子则特判 
        write(ans);
        putchar('\n');
    }
    return 0;
}