Minimal Power of Prime

解题思路

先打\(N^\frac{1}{5}\)内的素数表，对于每一个n，先分解\(N^\frac{1}{5}\)范围内的素数，分解完后n变为m，如果m等于1，那么答案就是\(N^\frac{1}{5}\)内分解的素数里的最小数量k。否则，继续分解，此时用来分解的质数都是大于\(N^\frac{1}{5}\)的，所以最多有4个质数相乘，所以只有三种情况：\(P^4\),\(P^3\),\(P^2\),\(P^2*Q^2\)，以及答案为1的情况(P,Q为大于\(N^\frac{1}{5}\)的质数)。对于前两种情况，分别看\(m^\frac{1}{4}\)，\(m^\frac{1}{3}\)是否是整数，对于三四种情况，其实是一样的，只要看\(m^\frac{1}{2}\)是不是整数就行了，前四种情况都不是，那么答案就是1。

代码如下

#include 
    
     #define INF 0x3f3f3f3fusing namespace std;typedef long long ll;inline int read(){    int res = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        res = (res << 3) + (res << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -res : res;}ll p(ll a, int b){    ll ans = 1;    for(int i = 1; i <= b; i ++)        ans *= a;    return ans;}int main(){    int t;    t = read();    vector
     
       vec;    for(int i = 2; i <= 4000; i ++){        bool flg = true;        for(int j = 2; j <= sqrt(i); j ++){            if(i % j == 0){                flg = false;                break;            }        }        if(flg)            vec.push_back(i);    }    while(t --){        ll n;        scanf("%lld", &n);        int ans = 100;        for(int i = 0; i < vec.size(); i ++){            int t = vec[i];            int cnt = 0;            while(n % t == 0){                n /= t;                ++cnt;            }            if(cnt)                ans = min(ans, cnt);        }        if(n == 1)            printf("%d\n", ans);        else {            for(int i = 4; i >= 1; i --){                if(i == 1)                    printf("1\n");                else {                    ll x = max((ll)pow(n, 1.0/i) - 5, 1LL);                    bool flg = true;                    ll m = p(x, i);                    while(m < n){                        ++ x;                        m = p(x, i);                    }                    if(m == n){                        printf("%d\n", min(ans, i));                        break;                    }                }            }        }    }    return 0;}