题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=6623
题目:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
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
解题思路:
质因子分解,直接做绝对会T。
即然不行,那呢,1e18开五次根=3980,不到3981,大概估算一下,如果统计完数x的1-4000内的质因子,一共550个质因子,若x有大于4000的质因子,那么x的因子可以分解成,或, 或,p为大于4000的质数,最高p的四次,否则就超过1e18, 所以在对x进行4000以内的质因子分解之后,剩下的数x'直接分情况讨论即可。
能分解成,或, 或,说明x'开4,或3, 或2次之后为整数,重点是要判断开次方后的结果是不是整数,这就涉及到精度的问题了,尤其是pow(x, 1.0/3)时结果更加不准确。且如果用pow(a,b)时如a为位数超过16的long long 类型的数,那么long long 转化成double 的结果其实是错误的,有误差的,可以用powl或者自己写个pow函数(判断函数)。
和这两种情况有点重复,要先判断开完4次是否为整数,再判断开2次的。
时间复杂度O(5e4*550)=O(3e7)
ac代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4000;
typedef long long ll;
bool vis[maxn+10] = {false};
int prime[maxn+10];
int cnt, ans;
ll x;
//线性筛法
void get_prime()
{
for(int i = 2; i <= maxn; i++)
{
if(!vis[i])
prime[++cnt] = i;
for(int j = 1; j <= cnt && (ll)i * prime[j] <= maxn; j++)
{
vis[(ll)i * prime[j]] = 1;
if(i % prime[j] == 0)
break;
}
}
}
void div(ll &x)
{
for(int i = 1; i <= cnt && prime[i] <= x; i++)
{
if(x % prime[i] == 0)
{
int tmp = 0;
while(x % prime[i] ==0)
{
tmp++;
x /= prime[i];
}
ans = min(ans, tmp);
}
}
}
ll mul(ll a, ll b)
{
ll res = 1;
while(b--) res *= a;
return res;
}
bool judge(int k)
{
//或者将所有的(ll)powl换成mul,超过16位的long long 转 double 会出错,可转成long double
ll p = (ll)powl(x, 1.0/k);
while((ll)powl(p+1, k) <= x)
p++;
return (ll)powl(p, k) == x;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
get_prime();
int t;
scanf("%d", &t);
while(t--)
{
ans = 100;
scanf("%lld", &x);
if (x == 1) ans = 0;
div(x);
if (x != 1) // 没有质因子分解完全
{
bool flag = 0;
for(int k = 4; k >= 2; k--) //从k=4先开始判断,p^4 优先 (p^2)^2
if(judge(k))
{
ans = min(ans, k);
flag = 1;
break;
}
if(!flag) ans = 1;
}
printf("%d\n", ans);
}
return 0;
}