题目:
- 输入x,输出使x = b ^ p的最大的p
- 先质因数分解,res=gcd(c1,c2...cm)就是答案,注意如果n是负数,res只能是奇数,所以先按正数计算,再把结果一直除2到奇数。还要特判1。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
#define rep(i, a, n) for(int i = a; i <= n; ++ i)
#define per(i, a, n) for(int i = n; i >= a; -- i)
typedef long long ll;
const int N = 5e5 + 105;
const int mod = 998244353;
const double Pi = acos(- 1.0);
const int INF = 0x3f3f3f3f;
const int G = 3, Gi = 332748118;
ll qpow(ll a, ll b) { ll res = 1; while(b){ if(b) res = (res * a) % mod; a = (a * a) % mod; b >>= 1;} return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
//
int T;
ll n;
ll p[N], c[N];
ll m;
void div(ll x){
m = 0;
for(ll i = 2; i * i<= x; ++ i){
if(n % i == 0){
p[ ++ m] = i, c[m] = 0;
while(n % i == 0) n /= i, c[m] ++;
}
}
if(n > 1) p[++ m] = n, c[m] = 1;
}
int main()
{
scanf("%d",&T);
rep(Case,1,T) {
int flag = 0;
scanf("%lld",&n);
if(n == 1){
printf("Case %d: 1\n",Case);
continue;
}
if(n < 0){
n = -n;
flag = 1;
}
ll res = 0;
div(n);
if(m == 1) res = c[m];
else{
rep(i,1,m){
res = gcd(res, c[i]);
}
}
if(flag){
while(res % 2 == 0) res /= 2;
}
printf("Case %d: %lld\n",Case,res);
}
return 0;
}