题目:
给出 x 求出最大的p 满足 x = b ^ p;因为p 最大是 32,所以枚举 p,如果一个数本身是素数,那么一定输出 1,注意如果 x < 0时,p 不可能是 偶数
View Code
1 typedef long long ll; 2 bool isprime(ll a) 3 { 4 ll i; 5 for(i = 2; i * i <= a; i++) 6 { 7 if(a % i == 0) return false; 8 } 9 return true;10 }11 int main()12 {13 ll x;14 int p;15 while(cin>>x)16 {17 if(x == 0) break;18 ll tx = x;19 if(tx < 0) tx = -tx;20 if(isprime(tx)) {cout<<"1\n";continue;}21 if(x > 0)22 {23 for(p = 32; p >= 1; p--)24 {25 int b = floor(pow(x,1.0 / p) + 0.5);26 int tem = p;27 ll res = 1;28 while(tem --)29 {30 res *= b;31 }32 if(res == x) break;33 }34 }35 else if(x < 0)36 {37 x = -x;38 for(p = 32; p >= 1; p--)39 {40 if(p % 2 == 0) continue;41 int b = floor(pow(x,1.0 / p) + 0.5);42 int tem = p;43 ll res = 1;44 while(tem --)45 {46 res *= b;47 }48 if(res == x) break;49 }50 }51 cout<<
纯数学的方法就是:找出 m 的所以质因子,然后求出 质因子幂数的最大公约数
写了好长时间都wa了,不知道自己错哪了,先贴一下,终于发现,原来对于负数时,我一开始的处理时,只要是个偶数就直接输出 1,这样是不对的,比如 -1073741824,计算出 temp = 30,但是 可以让 temp = 15,然后 ( -4) ^ 15 = -1073741824,看了好长时间,无意的试这个例子才发现自己错了
View Code
1 typedef long long ll; 2 const int N = 100000; 3 int prime[N]; 4 bool vis[N + 1]; 5 int sum[N]; 6 int num,tnum; 7 int flag; 8 void is_prime() 9 {10 int i,j;11 for(i = 2; i <= N; i++)12 {13 if(!vis[i]) prime[num ++] = i;14 for(j = 2; j * i <= N; j++)15 {16 if(vis[i * j]) continue;17 vis[i * j] = true;18 }19 }20 }21 void cal(ll m)22 {23 int i;24 for(i = 0; i < num; i++)25 {26 if(m == 1) break;27 if(m % prime[i] == 0)28 {29 int tsum = 0;30 while(m % prime[i] == 0)31 {32 tsum ++;33 m /= prime[i];34 }35 sum[tnum ++] = tsum;36 }37 }38 if(m != 1) sum[tnum ++] = 1;39 }40 ll gcd(ll a,ll b)41 {42 if(!b) return a;43 else return gcd(b,a % b);44 }45 int main()46 {47 num = 0;48 is_prime();49 int i;50 ll n;51 while(cin>>n)52 {53 if(n == 0) break;54 int mark = 0;55 if(n < 0) {mark = 1; n = -n;}56 _clr(sum,0);57 tnum = 0;58 flag = 0;59 cal(n);60 for(i = 0; i < tnum; i++)61 {62 if(sum[i] == 1) {flag = 1;break;}63 }64 if(flag) {cout<<"1\n";continue;}65 ll temp = sum[0];66 for(i = 1;i < tnum; i++)67 {68 ll kemp = gcd(temp,sum[i]);69 temp = kemp;70 }71 if(mark)72 {73 while(temp % 2 == 0) temp /= 2;74 if(temp != 1) cout<<