LightOJ - 1220（n=b^k时最大的k，GCD）

Dr. Mob has just discovered a Deathly Bacteria. He named it RC-01. RC-01 has a very strange reproduction system. RC-01 lives exactlyx days. Now RC-01 produces exactly p new deadly Bacteria wherex = b^p (where b, p are integers). More generally,x is a perfect p^th power. Given the lifetimex of a mother RC-01 you are to determine the maximum number of new RC-01 which can be produced by the mother RC-01.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a line containing an integer x. You can assume thatx will have magnitude at least 2 and be within the range of a 32 bit signed integer.

Output

For each case, print the case number and the largest integer p such thatx is a perfect p^th power.

Sample Input

3

17

1073741824

25

Sample Output

Case 1: 1

Case 2: 30

Case 3: 2

题意：给你一个数n，这个n一定等于b^k，让你求满足条件的最大的k

这个题有个规律：令n等于p1^e1*p2^e2*.....*pn^en，则最大的k为gcd（e1,e2,e3,.......,en）;

代码：

#include <iostream> #include <stdio.h> #include <math.h> #include <string.h> #include <vector> #include <algorithm> #include <queue> #include <map> using namespace std; typedef long long LL; #define fi first #define se second const LL MAXN=1e5+23; LL prime[MAXN],total; bool isprime[MAXN]; void make() { LL m=MAXN-3; memset(isprime,true,sizeof(isprime)); isprime[0]=isprime[1]=false; total=0; for(int i=2;i<=m;i++) { if(isprime[i])prime[++total]=i; for(int j=1;j<=total&&i*prime[j]<=m;j++) { isprime[i*prime[j]]=false; if(i%prime[j]==0)break; } } } LL gcd(LL a,LL b) { if(b==0)return a; else return gcd(b,a%b); } // 4294967296 int main() { LL n; make(); int T,cas=0; scanf("%d",&T); while(T--) { int flag=0; scanf("%lld",&n); if(n>0)flag=1; n=abs(n); LL ans=0; printf("Case %d: ",++cas); if(flag) { for(int i=1;i<=total&&prime[i]*prime[i]<=n;i++) { LL s=0; while(n%prime[i]==0) { s++; n/=prime[i]; } ans=gcd(ans,s); } if(n>1)ans=1; printf("%lld\n",ans); } else { for(int i=1;i<=total&&prime[i]*prime[i]<=n;i++) { LL s=0; while(n%prime[i]==0) { s++; n/=prime[i]; } ans=gcd(ans,s); } if(n>1)ans=1; while(ans%2==0) { ans/=2; } printf("%lld\n",ans); } } return 0; } 这是最常用的做法（然鹅我一开始并不知道……）

我自己的做法：n=sqrt（1<<32）,nlog(n)打个表，然后直接查：

#include <iostream> #include <stdio.h> #include <math.h> #include <string.h> #include <vector> #include <algorithm> #include <map> using namespace std; typedef long long LL; const LL MAXN=((LL)1<<32); #define fi first #define se second map<LL,LL>s; void init() { for(LL i=2;i<=100000;i++) { LL k=1; for(LL j=i;j<=MAXN*2;j*=i) { s[j]=max(k,s[j]);//if(i==2)printf("j=%lld k=%lld s=%lld\n",j,k,s[j]); k++; } //if(i==17)puts(""); } } int main() { //printf("%lld\n",MAXN); init(); int T,cas=0; scanf("%d",&T); while(T--) { LL n; scanf("%lld",&n); LL N=n>0?n:-n; if(s[N]==0)s[N]=1; printf("Case %d: ",++cas); if(n<0) { if(s[N]%2==1) { printf("%lld\n",s[N]); } else { LL k=s[N]; while(k%2==0)k/=2; printf("%lld\n",k); } } else printf("%lld\n",s[N]); } return 0; } 代码写得丑加上打表范围开大了加上代码写的巨丑导致比第一种方法慢了巨多。。。。。。

注意这个题有个巨坑就是n可为负（讲道理他也确实没说n一定是正的。。。。。。）

n<0时你得到的k必须是奇数，这个时候就要把得到的k仔细算一算做个转换了

大概就是这样了。。。