首页 > 代码库 > POJ 1730 Perfect Pth Powers（唯一分解定理）
POJ 1730 Perfect Pth Powers（唯一分解定理）
http://poj.org/problem?id=1730
题意：
给出一个n，a=b^p，求出最大p值。
思路：
首先利用唯一分解定理，把n写成若干个素数相乘的形势。接下来对于每个指数求最大公约数，该公约数就是所能到达的最大p值。
有一点要注意的是如果n为负数的话，如果当前p值为偶数，就一直除2直到p为奇数。
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 8 const int maxn = 70000; 9 10 long long n;11 int vis[maxn];12 int prime[7000];13 int cnt;14 15 void get_prime()16 {17 cnt = 0;18 int m = sqrt(maxn + 0.5);19 for (int i = 2; i < maxn; i++)20 {21 if (!vis[i])22 {23 prime[cnt++] = i;24 for (int j = i; j < maxn; j += i)25 vis[j] = 1;26 }27 }28 }29 30 31 int gcd(int a, int b)32 {33 if (a < b) return gcd(b, a);34 if (b == 0) return a;35 return gcd(b, a % b);36 }37 38 int main()39 {40 //freopen("D:\\txt.txt", "r", stdin);41 get_prime();42 while (~scanf("%lld", &n) && n)43 {44 int flag = 0;45 int ans = 0;46 if (n < 0)47 {48 n = -n;49 flag = 1;50 }51 int flag2 = 1;52 for (int i = 0; i < cnt && n>1; i++)53 {54 if (n%prime[i] == 0)55 {56 int ret = 0;57 while (n%prime[i] == 0)58 {59 n /= prime[i];60 ret++;61 }62 ans = gcd(ans, ret);63 }64 }65 if (n > 1) ans = 1;66 if (flag)67 {68 while (ans % 2 == 0) ans /= 2;69 }70 printf("%d\n", ans);71 }72 }
POJ 1730 Perfect Pth Powers（唯一分解定理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。