merging dua II audio interface_power of one

全栈程序员站长

发布于 2022-09-29 11:56:26

1870

发布于 2022-09-29 11:56:26

大家好，又见面了，我是你们的朋友全栈君

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=6623 Minimal Power of Prime

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1935 Accepted Submission(s): 437

Problem Description You are given a positive integer n > 1. Consider all the different prime divisors of n. Each of them is included in the expansion n into prime factors in some degree. Required to find among the indicators of these powers is minimal.

Input The first line of the input file is given a positive integer T ≤ 50000, number of positive integers n in the file. In the next T line sets these numbers themselves. It is guaranteed that each of them does not exceed 10^18.

Output For each positive integer n from an input file output in a separate line a minimum degree of occurrence of a prime in the decomposition of n into simple factors.

Sample Input

Sample Output

这道题题意是，几个素数的几次幂相乘，求最小的幂。比如108=4*27=22*33,min=2; 那先打一个素数表求出1-4000的素数个数，由于数有1018, 要是没除尽的话，因子最多也就4个了，所以幂数大于1的情况有p14，p13, p12 ， p12*p22, Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps=1e-5;
int P4 ( ll x )
{
    ll l=floor(pow( x, 1.0/4 )+eps);
    ll sum = l*l*l*l;
    return sum==x;
}
int P3 ( ll x )
{
    ll l=floor(pow( x, 1.0/3 )+eps);
    ll sum = l*l*l;
    return sum==x;
}
int P2 ( ll x )
{
    ll l=floor(pow( x, 1.0/2 )+eps);
    ll sum = l*l;
    return sum==x;
}
int isprime[4010];
int primes[4010],len;
void get_prime()
{
    len = 0;
    memset(isprime,true,sizeof(isprime));
    isprime[0] = false;
    isprime[1] = false;
    for( int i=2 ; i<4010 ; i++ )
    {
        if( isprime[i] )
            primes[len++] = i;
        for( int j=0 ; j<len ; j++ )
        {
            if( i*primes[j]>=4010 )
                break;
            isprime[i*primes[j]]=false;
            if( i%primes[j]==0 )
                break;
        }
    }
}

int main()
{
    get_prime();
    int repeat;
    cin>>repeat;
    while(repeat--)
    {
        ll n;
        cin>>n;
        int ans = 100;
        for( int i=0; i<len; i++ )
        {
            if(n<primes[i])
                break;
            if(n%primes[i]==0)
            {
                int tmp=0;
                while(n%primes[i]==0)
                {
                    n/= primes[i];
                    tmp++;
                }
                ans=min(ans,tmp);
            }
        }
        if( n==1 )
        {
            printf("%d\n",ans);
        }
        else
        {
            if(ans>4&&P4(n))
            {
                printf("4\n");
            }
            else if(ans>3&&P3(n))
            {
                printf("3\n");
            }
            else if(ans>2&&P2(n))
            {
                printf("2\n");
            }
            else
            {
                printf("1\n");
            }
        }
    }
    return 0;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/192994.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年9月16日，如有侵权请联系 cloudcommunity@tencent.com 删除

https