 signed

QiShunwang

“诚信为本、客户至上”

# Mysterious Bacteria(唯一质因子解+素数筛)

2021/5/14 21:57:19   来源：

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 = b的p次方 (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
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.

Output
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

AC代码：

``````#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
typedef long long ll;
int prime[N],ans=0;
bool ver[N];

void Prime()
{
memset(ver,true,sizeof(ver));
ver=false;
for(int i=2;i<N;i++)
{
if(ver[i])
{
prime[ans++]=i;
for(int j=i;1LL*i*j<N;j++)
ver[i*j]=false;
}
}
}

int gcd(int a,int b)
{
return a%b==0?b:gcd(b,a%b);
}

int main()
{
int t,p=0;
ll n;
Prime();
cin>>t;
while(t--)
{
p++;
cin>>n;
int f=0;
if(n<0)
{
n=-n;
f=1;
}
int x,k=0;
for(int i=0;i<ans&&prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]==0)
{
x=0;
while(n%prime[i]==0)
{
x++;
n/=prime[i];
}
if(k==0)
k=x;
else
k=gcd(k,x);
}
}
if(n>1)
k=gcd(k,1);
if(f==1)
{
while(k%2==0)
k=k/2;
}
printf("Case %d: %d\n",p,k);
}
return 0;
}
``````