大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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
5
2
12
108
36
65536
Sample Output
1
1
2
2
16
这道题题意是 ，几个素数的几次幂相乘，求最小的幂。
比如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.net/192994.html原文链接：https://javaforall.net
