暴力就行了，找出素因子，正的最多是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+5; const int INF=0x3f3f3f3f; bool v[N]; int prime[6000],cnt; void getprime(){ for(int i=2;i*i<=N-5;++i) if(!v[i]) for(int j=i*i;j<=N-5;j+=i) v[j]=1; for(int i=2;i<=N-5;++i) if(!v[i])prime[++cnt]=i; } vector<int>g; int main() { getprime(); int cas=0,T; scanf("%d",&T); while(T--){ int t,n; scanf("%d",&n),t=abs(n); g.clear(); for(int i=1;i<=cnt&&prime[i]<=t/prime[i];++i){ if(t%prime[i])continue; int tot=0; while(t%prime[i]==0)t/=prime[i],++tot; g.push_back(tot); } if(t>1)g.push_back(1); int ans=1; if(n<0){ for(int i=31;i>1;i-=2){ bool flag=0; for(int j=0;j<g.size();++j){ if(g[j]%i){ flag=1; break; } } if(!flag){ ans=i; break; } } } else{ for(int i=30;i>1;--i){ bool flag=0; for(int j=0;j<g.size();++j){ if(g[j]%i){ flag=1; break; } } if(!flag){ ans=i; break; } } } printf("Case %d: %d ",++cas,ans); } return 0; }