当前位置: 代码迷 >> 综合 >> LightOJ - 1220 Mysterious Bacteria 唯一分解定理
  详细解决方案

LightOJ - 1220 Mysterious Bacteria 唯一分解定理

热度:93   发布时间:2024-01-15 06:59:26.0

Mysterious Bacteria
题目描述
Dr. Mob has just discovered a Deathly Bacteria. He named it RC-01. RC-01 has a very strange reproduction system. RC-01 lives exactly x days. Now RC-01 produces exactly p new deadly Bacteria where x = bp (where b, p are integers). More generally, x is a perfect pth power. Given the lifetime x of a mother RC-01 you are to determine the maximum number of new RC-01 which can be produced by the mother RC-01.

输入
Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a line containing an integer x. You can assume that x will have magnitude at least 2 and be within the range of a 32 bit signed integer.

输出
For each case, print the case number and the largest integer p such that x is a perfect pth power.

样例
Sample Input
3
17
1073741824
25
Sample Output
Case 1: 1
Case 2: 30
Case 3: 2
 

题意:x=b^p  给出x求出最大的p

分析:

唯一分解定理:

每一个大于1的正整数n都可以唯一地写成素数的乘积,在乘积中的素因子按照非降序排列,正整数n的分解式n=(p1^α1)*(p2^α2)*(p3^α3)* ....... *(pk^αk)称为n的标准分解式,其中p1,p2,p3......pk是素数,p1<p2<p3.....,且α1,α2,α3.......是正整数。

接下来,最小的p就为gcd(α1,α2,α3......αk),为什么呢?举两个个例子,

24 = 2^3 * 3^1,p应该是gcd(3, 1) = 1,即24 = 24^1,想一想是不是只能把2^3合并到3^1次方里来

324 = 3^4*2^2,p应该是gcd(4, 2) = 2,即324 = 18^2,想一想是不是把3^4合并到2^2次方里来

本题有一个坑点:就是x可能为负数,如果x为负数的话,x = b^q, q必须使奇数,因为偶数的偶数次方大于正数,所以将x转化为正数求得的解如果是偶数的话必须将其一直除2转化为奇数

 

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<stack>
#include<map>
#define PI acos(-1.0)
#define in freopen("in.txt", "r", stdin)
#define out freopen("out.txt", "w", stdout)
#define kuaidian ios::sync_with_stdio(0);using namespace std;
typedef long long ll;     
const ll N = 5e4+7;
int fac[N],flag;   
ll prime[N] = {0},num_prime = 0;  //prime存放着小于N的素数   
int isNotPrime[N] = {1, 1};        // isNotPrime[i]如果i不是素数,则为1 
int Prime()    
{     for(ll  i = 2 ; i < N ; i ++)       {            if(! isNotPrime[i])               prime[num_prime ++]=i;  //无论是否为素数都会下来     for(ll  j = 0 ; j < num_prime && i * prime[j] <  N ; j ++){               isNotPrime[i * prime[j]] = 1;  if( !(i % prime[j] ) )  //遇到i最小的素数因子//关键处1                  break;           }        }        return 0;   
}  int gcd(int a, int b) {return b == 0 ? a : gcd(b, a%b);
}//与素数筛选一起用的质数分解
///将x分解为式n=(p1^α1)*(p2^α2)*(p3^α3)* ....... *(pk^αk)
///fac求解保存底数p1或者指数α1
void Dec(ll x)
{int cnt = 0;for(int i=0; prime[i]*prime[i]<=x&&i<num_prime; i++){if(x%prime[i]==0){int num=0;while(x%prime[i]==0){num++;x /= prime[i];} fac[cnt++] =num;///如果fac保存的为底数因子(num无用),改为fac[cnt++]=x;}if(x==1) break;}if(x > 1)fac[cnt++] = 1;     ///如果fac保存的为底数因子,改为fac[cnt++]=xll ans=0;for(int i = 0; i < cnt; ++i) {ans = gcd(ans, fac[i]);}if(!flag) while(ans % 2 == 0) ans /= 2;cout << ans << endl;
}int main() {int T;Prime();cin >> T;ll n;for(int tt = 1; tt <= T; ++tt) {cin >> n;if(n > 0) flag = 1;else { flag = 0;n *= (-1);}cout << "Case " << tt << ": ";Dec(n);}return 0;
}

 

  相关解决方案