LightOJ 1220 Mysterious Bacteria 水题

暴力就行了，找出素因子，正的最多是30，然后负的最多是31（这一点wa了一次）

#include <cstdio>

#include <iostream>

#include <ctime>

#include <vector>

#include <cmath>

#include <map>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long LL;

const int N=5e4+;

const int INF=0x3f3f3f3f;

bool v[N];

int prime[],cnt;

void getprime(){

  for(int i=;i*i<=N-;++i)

    if(!v[i])

      for(int j=i*i;j<=N-;j+=i)

        v[j]=;

  for(int i=;i<=N-;++i)

  if(!v[i])prime[++cnt]=i;

}

vector<int>g;

int main()

{

    getprime();

    int cas=,T;

    scanf("%d",&T);

    while(T--){

      int t,n;

      scanf("%d",&n),t=abs(n);

      g.clear();

      for(int i=;i<=cnt&&prime[i]<=t/prime[i];++i){

          if(t%prime[i])continue;

          int tot=;

          while(t%prime[i]==)t/=prime[i],++tot;

          g.push_back(tot);

      }

      if(t>)g.push_back();

      int ans=;

      if(n<){

      for(int i=;i>;i-=){

        bool flag=;

        for(int j=;j<g.size();++j){

          if(g[j]%i){

            flag=;

            break;

          }

        }

        if(!flag){

          ans=i;

          break;

        }

      }

     }

     else{

      for(int i=;i>;--i){

        bool flag=;

        for(int j=;j<g.size();++j){

          if(g[j]%i){

            flag=;

            break;

          }

        }

        if(!flag){

          ans=i;

          break;

        }

      }

     }

      printf("Case %d: %d\n",++cas,ans);

    }

    return ;

}