lightoj1220,质因数分解+gcd
给你一个数x = b^p,求p的最大值
x = p1^x1*p2^x2*p3^x3*...*ps^xs
p = gcd(x1, x2, x3, ... , xs);
比如：24 = 2^3*3^1，p应该是gcd(3, 1) = 1,即24 = 24^1
324 = 3^4*2^2,p应该是gcd(4, 2) = 2,即324 = 18^2
正数：质因数分解求幂的gcd
负数：负数如果平方就会变正数，所以结果为负的不能存在幂为2的倍数
#include <bits/stdc++.h>
using namespace std;
//const long long INF=100000000;
const int N=100005;
long long t,x;
bool st[N];
int prime[N],cnt=0;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
void makeTable(){
for(int i=2;i<=N-1;i++){
if(!st[i]) prime[cnt++]=i;
for(int j=0;prime[j]<=(N-1)/i;j++){
st[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
}
int main(int argc, char** argv) {
cin>>t;
makeTable();
for(int i=1;i<=t;i++){
cin>>x;
bool isneg=false;
if(x<0) isneg=true,x=-x;
int ans=0,a;
for(int j=0;j<cnt&&prime[j]<=x/prime[j];j++){
if(x%prime[j]==0){
a=0;
while(x%prime[j]==0){
a++;
x/=prime[j];0
}
if(ans) ans=gcd(ans,a);
else ans=a;//第一次直接赋值
}
}
if(x>1) ans=1;
if(isneg) {
while(ans%2==0){
ans/=2;//结果为负的不能存在幂为2的倍数
}
}
printf("Case %d: %d\n",i,ans);
}
return 0;
} 
查看6道真题和解析
