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

Dear 丶 2021-11-14 15:04 180阅读 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;
    }