首页 > 代码库 > UVA - 10622 Perfect P-th Powers
UVA - 10622 Perfect P-th Powers
Description
Problem E: Perfect Pth Powers
We say that x is a perfect square if, for some integer b,x = b^2. Similarly,x is a perfect cube if, for some integerb, x = b^3. More generally,x is a perfect pthpower if, for some integer b, x = b^p. Given anintegerx you are to determine the largest p such that xis a perfect pth power.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 therange of a (32-bit) int inC, C++, and Java. A line containing 0 follows the last test case.
For each test case, output a line giving the largest integer p such thatx isa perfect pth power.
Sample Input
17 1073741824 25 0
Output for Sample Input
1 30 2
题意:求x=b^p,的 最大的p
思路:首先将n分解质因数,然后找因数个数的gcd就是了,负数的话,一直除以2,直到答案是奇数的时候
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> typedef long long ll; using namespace std; const int maxn = 333333; ll n; int prime[maxn], vis[maxn], cnt = 0; int gcd(int a, int b) { return b==0?a:gcd(b, a%b); } int solve() { ll tmp = n; if (n < 0) n = -n; int ans = 0; for (int i = 0; i < cnt && prime[i] <= n; i++) { int count = 0; while (n % prime[i] == 0) { count++; n /= prime[i]; } ans = gcd(ans, count); } if (ans == 0) ans = 1; if (tmp < 0) { while (ans % 2 == 0) ans /= 2; } return ans; } int main() { for (int i = 2; i < maxn; i++) { if (vis[i]) continue; prime[cnt++] = i; for (int j = i; j < maxn; j += i) vis[j] = 1; } while (scanf("%lld", &n) != EOF && n) { printf("%d\n", solve()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。