LightOJ1220 Mysterious Bacteria(思维+唯一分解)

2023-09-25 10 0

题目大意:

给你一个整数n(可能为负数),让你求满足a^p=n的最大的p

思路:

当n是正数时,直接对n进行素因子分解,在对它的素因子的个数进行gcd,比如12=2^2*3,gcd(2,1)就是最大的p;

当n是负数时,则p的值一定是奇数,因为一个数的偶数次方一定为整数,因此需要将它的素因子个数全都化为奇数

这题主要在于n为负数时的思考!


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<climits>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn = 1000100;
bool vis[maxn], flag;
ll prim[maxn/10], n;
int m;
void initPrime()
{m = 0;for(ll i = 2; i < maxn; i++){if(!vis[i])prim[m++] = i;for(ll j = i*i; j < maxn; j += i)vis[j] = true;}
}
int solve(ll x)
{int ans = 0;for(int i = 0; i < m && prim[i]*prim[i] <= x; i++){int res = 0;while(x % prim[i] == 0&&x){x /= prim[i], res++;}if(flag)while(res%2==0&&res)res /= 2;if(res && !ans)ans = res;else if(res)ans = __gcd(ans, res);}if(x > 1)ans = 1;return ans;
}
int main()
{int T;initPrime();scanf("%d", &T);for(int kase = 1; kase <= T; kase++){scanf("%lld", &n);flag = false;if(n < 0)n = -n, flag = true;printf("Case %d: %d\n", kase, solve(n));}return 0;
}


代码编程
赞赏

相关文章

problem B【西安电子科技大学】
problem D【西安电子科技大学】
五道口地摊观察(2)
堆栈的使用【吉林大学】
【互动媒体专题设计】《打群架》——模拟《拥挤城市》
寻找大富翁【浙江大学】★