HDU - 6623 Minimal Power of Prime 因子幂最小（暴力+思维）-蒲公英云

HDU - 6623 Minimal Power of Prime 因子幂最小（暴力+思维）

Dear 丶 2021-11-14 15:04 249阅读 0赞

题意：输出n所有质因子幂的最小值。

分析：打出10000以内的素数，把 n 分解质因数，如果 n 分解完不为1或者最小幂已经为1，可以直接输出结果，否则分4种情况，n是一个质数的4次方，n是一个质数的3次方，n是一个质数的2次方，n是一个或多个不同质数相乘得到，讨论出前三种情况即可。注意精度问题。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4+5;
int vs[N],p[N],cnt,t;
void init() {
    for (int i = 2; i <= N; i++) {
        if (!vs[i]) p[++cnt] = i;
        for (int j = 1; j <= cnt && p[j] * i <= N; j++) {
            vs[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}
ll qp(ll x, int y) {
    ll ans = 1;
    for(int i=1;i<=y;i++) ans*=x;
    return ans;
}
ll n;
int main() {
    scanf("%d",&t);
    init();
    while (t--) {
        scanf("%lld", &n);
        int ans = 1e9;
        for (int i = 1; i <= cnt && p[i] <= n; i++)
        if (n % p[i] == 0) {
            int tp = 0;
            while (n % p[i] == 0) tp++, n /= p[i];
            ans = min(ans, tp);
        }
        if (n == 1 || ans==1 ) {
            printf("%d\n", ans);
            continue;
        }
        int x = pow(n, 1.0 / 4);
        if (qp(x, 4) == n || qp(x + 1, 4) == n || qp(x - 1, 4) == n) ans = min(ans, 4);
        else {
            x = pow(n, 1.0 / 3);
            if (qp(x, 3) == n || qp(x + 1, 3) == n || qp(x - 1, 3) == n) ans = min(ans, 3);
            else {
                int x = pow(n, 0.5);
                if (qp(x, 2) == n || qp(x + 1, 2) == n || qp(x - 1, 2) == n) ans = min(ans, 2);
                else ans = 1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}