UVA 10622 - Perfect P-th Powers(数论)

本文主要是介绍UVA 10622 - Perfect P-th Powers(数论)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA 10622 - Perfect P-th Powers

题目链接

题意：求n转化为b^p最大的p值

思路：对n分解质因子，然后取所有质因子个数的gcd就是答案，但是这题有个坑啊，就是输入的可以是负数，负数的情况比较特殊，p只能为奇数，这时候是要把答案不断除2除到为奇数即可。

代码：

#include <stdio.h>
#include <string.h>
#include <math.h>long long n;
int prime[333333], vis[333333], m = 0;
int gcd(int a, int b) {if (b == 0) return a;return gcd(b, a % b);
}int solve() {long long nn = n;if (n < 0) n = -n;int ans = 0;for (int i = 0; i < m && 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 (nn < 0) {while (ans % 2 == 0) {ans /= 2;		}}return ans;
}int main() {for (int i = 2; i < 333333; i++) {if (vis[i]) continue;prime[m++] = i;for (int j = i; j < 333333; j += i) {vis[j] = 1;}}while (~scanf("%lld", &n) && n) {printf("%d\n",  solve());}return 0;
}

这篇关于UVA 10622 - Perfect P-th Powers(数论)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---