首页 > 代码库 > poj 1730Perfect Pth Powers(分解质因数)
poj 1730Perfect Pth Powers(分解质因数)
Perfect Pth Powers
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 16746 | Accepted: 3799 |
Description
We say that x is a perfect square if, for some integer b, x = b2. Similarly, x is a perfect cube if, for some integer b, x = b3. More generally, x is a perfect pth power if, for some integer b, x = bp. Given an integer x you are to determine the largest p such that x is a perfect pth power.
Input
Each test case is given by a line of input containing x. The value of x will have magnitude at least 2 and be within the range of a (32-bit) int in C, C++, and Java. A line containing 0 follows the last test case.
Output
For each test case, output a line giving the largest integer p such that x is a perfect pth power.
Sample Input
17 1073741824 25 0
Sample Output
1 30 2
题意:给出一个整数x,把x写成x=a^p,求p最大是多少?
分析:把x分解质因数,x = a1^b1 * a2^b2 … ak^bk,则最终结果为b1,b2,…bk的最大公约数。注意x有可能是负数。
如果x是负数,则要把求得的答案一直除以2,知道结果一个奇数,因为一个数的偶数次方不可能是负数。
#include <cstdio> #include <cmath> #include <cstring> const int N = 66700; int is[N]; int prime[7000], prime_cnt; void get_prime() { for(int i = 0; i < N; i++) is[i] = 1; is[0] = is[1] = 0; prime_cnt = 0; int m = (int)sqrt(N + 0.5); for(int i = 2; i < N; i++) { if(is[i]) { prime[prime_cnt++] = i; if(i <= m) { for(int j = i * i; j < N; j += i) is[j] = 0; } } } } int gcd(int a, int b) { if(a < b) return gcd(b, a); if(b == 0) return a; return gcd(b, a % b); } int main() { get_prime(); long long n; //不知道当n为int时为什么会TLE while(~scanf("%lld", &n) && n) { int flag = 0; if(n < 0) { flag = 1; n = -n; } int ans = 0; for(int i = 0; i < prime_cnt && n > 1; i++) { if(n % prime[i] == 0) { int cnt = 0; while(n % prime[i] == 0) { n /= prime[i]; cnt++; } ans = gcd(ans, cnt); } } if(n > 1) ans = gcd(ans, 1); if(flag) { while(ans % 2 == 0) ans /= 2; } printf("%d\n", ans); } return 0; }
poj 1730Perfect Pth Powers(分解质因数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。