2019HDU多校Minimal Power of Prime—

题目

将 $n$（$1 < n \leq 10^{18}$）质因数分解，求质因数幂的最小值。

分析

直接质因数分解，不太行。

可以这样想，对小区间质因数分解，n变小了，再枚举答案。

打印1-10000之间的素数表然后质因数分解，分解完剩下的那个数，

两种质数（肯定大于 $10^4$）相乘，最多二次，合起来也是一个平方数；
三种或以上质数相乘，只可能为一次，不用考虑。
一种质数，最多为四次方，枚举四、三、二次方，如果都不是，就是单个质数

要注意：先看是4次方再看2次方（因为如果满足4次方一定满足2次方，但是满足4次方也满足2次方，2次方的话就不是质因数了），3次方无所谓，因为开3次方会损失精度，所以就二分一下。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n;

//返回n以内素数的个数

//埃氏筛法O(nloglogn)

const int maxn =  + ;

int prime[maxn];            //prime[i]表示第i个素数

bool is_prime[maxn + ];    //is_prime[i]为true表示i是素数

int sieve(int n)

{

    int cnt = ;

    for (int i = ; i <= n; i++)  is_prime[i] = true;

    is_prime[] = is_prime[] = false;

    for (int i = ; i <= n; i++)

    {

        if (is_prime[i])

        {

            prime[cnt++] = i;

            for (int j = i * i; j <= n; j += i)  is_prime[j] = false;  //i * i可能爆int

        }

    }

    return cnt;

}

bool is_three(ll n)    //是否能开立方

{

    ll l = , r = 1e6;

    while(l <= r)

    {

        ll mid = (l+r) >> ;

        ll tmp = mid*mid*mid;

        if(tmp == n)  return true;

        else if(tmp > n) r = mid-;

        else l = mid+;

    }

    return false;

}

int main()

{

    int cnt = sieve();  //筛出10000内的质数

    int T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%lld", &n);

        int ans = ;

        for(int i = ;i < cnt;i++)

        {

            if(n % prime[i] == )

            {

                int tmp = ;

                while(n % prime[i] == )

                {

                    n /= prime[i];

                    tmp++;

                }

                ans = min(tmp, ans);

            }

            if(n == ) break;

        }

        if(ans == ){ printf("1\n"); continue;}

        if(n == ){ printf("%d\n", ans); continue;}

        ll t1 = (ll)sqrt(n);

        ll t2 = (ll)sqrt(t1);

        if(t2*t2*t2*t2 == n)  ans = min(ans, );

        else if(t1*t1 == n)  ans = min(ans, );

        else if(is_three(n))  ans = min(ans , );

        else ans = min(ans, );

        printf("%d\n", ans);

    }

    return ;

}

参考链接：https://blog.csdn.net/lgz0921/article/details/97948432

巴特西

2019HDU多校Minimal Power of Prime——分段讨论&&思维

题目

分析

最新文章

热门文章