题意：x可以表示为bp, 求这个p的最大值，比如 25=52, 64=26, 然后输入x 输出 p
就是一个质因子分解、算法。（表示数据上卡了2个小时。）
合数质因子分解模板。
int num[];
int ind[];
int cnt=; for(int i=;n!=;++i)
{
if(n%i==)
{
num[cnt]=i; while(n%i==){ind[cnt]++;n/=i;} cnt++; }
if(i>)break;
}
if(n>){num[cnt]=n; ind[cnt++]=;}
两种方法：
方法一：时间最坏的时间复杂度是（大概10^8*n）就是这种方法，数据卡了很久，如果数据再给狠一点肯定不过，应为10^8在每一次都是一次。我估计数据有一个非常大素数，和比这个素数稍微少一些的数据，
当你选择if(i>10000)break； 这个判断条件时就有诟病， 不过还是过了
#include<cstdio>
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int main()
{
//int k=Prime();
int n;
while (scanf("%d", &n), n)
{
int cnt; bool flag = ;
int ans; bool first = ;
if (n < ){ flag = ; n = -n; }
for (int i = ; n!=; ++i)
{
if (n%i == )
{
cnt = ;
while (n%i == ){ n /= i; ++cnt; }
if (!first){ ans = cnt; first = ; }
else ans = gcd(ans, cnt);
}
if (i>)break;
}
if (n>)ans = ;
if (flag)while (ans % == )ans /= ;
printf("%d\n", ans);
}
}
方法二：欧拉筛+合数分解
时间复杂度：10^6+n
#include<cstdio>
const int N = 1e6;
int prime[N];
bool vis[N];
bool is_prime[N];
int Prime()
{
int cnt = ;
for (int i = ; i <= N; ++i)
{
if (!vis[i])
{
prime[cnt++] = i;
is_prime[i] = ;
}
for (int j = ; j < cnt&&i*prime[j] <= N; ++j)
{
vis[i*prime[j]] = ;
if (i%prime[j] == )break;
}
}
return cnt;
} int gcd(int a, int b){ return b == ? a : gcd(b, a%b); } int main()
{
int k=Prime();
int n;
while (scanf("%d", &n), n)
{
int cnt; bool flag = ;
int ans; bool first = ;
if (n < ){ flag = ; n = -n; }
for (int i = ; i<k; ++i)
{
if (n%prime[i] == )
{
cnt = ;
while (n%prime[i] == ){ n /= prime[i]; ++cnt; }
if (!first){ ans = cnt; first = ; }
else ans = gcd(ans, cnt);
}
}
if (n>)ans = ;
if (flag)while (ans % == )ans /= ;
printf("%d\n", ans);
}
}