merging dua II audio interface_power of one

全栈程序员-站长 • 2025年12月4日上午10:01 • 未分类 • 阅读 2

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

题目连接：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=2²*3³,min=2;
那先打一个素数表求出1-4000的素数个数，由于数有10¹⁸,
要是没除尽的话，因子最多也就4个了，所以幂数大于1的情况有p1⁴，p1³, p1² ， p1²*p2²,
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.net/192994.html原文链接：https://javaforall.net