lightoj 1220

亦凉 2022-08-10 09:45 26阅读 0赞

1220 - Mysterious Bacteria

<table> 
 <tbody> 
  <tr> 
   <td title="normal judge"><a href="http://lightoj.com/volume_submit.php?problem=1220" rel="nofollow"><img src="http://lightoj.com/images/submit1.png" alt=""> </a></td> 
   <td><a href="http://lightoj.com/volume_showproblem.php?problem=1220&amp;language=english&amp;type=pdf" rel="nofollow">PDF (English) </a></td> 
   <td><a href="http://lightoj.com/volume_problemstat.php?problem=1220" rel="nofollow">Statistics </a></td> 
   <td><a href="http://lightoj.com/forum_showproblem.php?problem=1220" rel="nofollow">Forum </a></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td>Time Limit: <span style="color:#B45F04">0.5 second(s)</span></td> 
   <td>Memory Limit: <span style="color:#B45F04">32 MB</span></td> 
  </tr> 
 </tbody> 
</table>

Dr. Mob has just discovered a Deathly Bacteria. He named itRC-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 themaximum 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 therange 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.

<table> 
 <tbody> 
  <tr> 
   <td> <h1>Sample Input</h1> </td> 
   <td> <h1>Output for Sample Input</h1> </td> 
  </tr> 
  <tr> 
   <td> <p>3</p> <p>17</p> <p>1073741824</p> <p>25</p> </td> 
   <td> <p>Case 1: 1</p> <p>Case 2: 30</p> <p>Case 3: 2</p> </td> 
  </tr> 
 </tbody> 
</table>

题意：给定x，让你找到一个最大的p，使得某个数的p次方正好是x。

分析：开始并不知道x还可能是负数，wrong了无数。。先说正数的情况，很自然的会想到把x进行因数分解，然后从每个质数的次方数中找到最大的p。多举几个例子就可以看出来最大的p就是每个质数的次方数的最小公倍数。。

对于负数的情况，显然负数的偶次幂是正数，如果算出来负数对应的正数的最大的p是偶数，那么应该把它不断除二直到它是奇数。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=50100;
    bitset<N> vis;
    int prime[N>>3];
    int cnt[N];
    int ans[N>>3];
    int p;
    int gcd(int a,int b)
    {
        return b==0? a : gcd(b,a%b);
    }
    int main()
    {
        for(int i=2;i<N;i++)
        {
            if(!vis[i])
            {
                prime[p++]=i;
                for(ll j = 1LL*i*i;j<N;j+=i) vis[j]=1;
            }
        }
        int T=in(),ii=1;
        ll n;
        while(T--)
        {
            scanf("%lld",&n);
            bool flag=0;
            if(n<0)n=-n,flag=1;
    
            mem(cnt,0);
            bool ok=1;
            int c=0;
            for(int i=0;i<p && 1LL*prime[i]*prime[i]<=n;i++)
            {
                if(n%prime[i]==0)
                {
                    ans[c++]=prime[i];
                    while(n%prime[i] == 0)
                    {
                        cnt[prime[i]]++;
                        n /= prime[i];
                    }
                }
            }
            if(n>1)
            {
                printf("Case %d: %d\n",ii++,1);
                continue;
            }
    
            int tmp = cnt[ans[0]];
            for(int i=1;i<c;i++)
            {
                tmp = gcd(tmp,cnt[ans[i]]);
            }
            if(flag && tmp%2==0)
            {
                while(tmp%2==0) tmp>>=1;
                printf("Case %d: %d\n",ii++,tmp);
                continue;
            }
            printf("Case %d: %d\n",ii++,tmp);
    
        }
        return 0;
    }