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 <bits/stdc++.h>

#define INF 0x3f3f3f3f

using 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<int> 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;

}

巴特西

2019杭电多校第四场hdu6623 Minimal Power of Prime

Minimal Power of Prime

解题思路

代码如下

最新文章

热门文章