2019杭电多校第四场1010 Minimal Power of Prime
程序员文章站
2024-03-21 15:10:58
...
题意
给你一个大于1的正整数n,这个正整数可以转换成n = p1^(k1) * p2^(k2) * …… * pn^(kn),其中p是质数, k是自然数,让你求k中的最大值
思路
当时和队友打的时候想的是先预处理1e6内的素数,但是后面被我们给否决了,会T飞。然后经过高人提点,才知道只要到质数筛选到1e4就好了。
对于n,先记录n在1e4前的k的最大值,1e4的素数筛完的最大值设为maxx之后,后面的只要用if判断一下就好了,因为最后的数字的最大的k也就是4次
先假设1e4的素数筛完之后的数为m
1.如果pow((int)sqrt(m), 2) == m
假设mm=int(sqrt(m)),如果pow(mm, 2) == m
那么k的最大值就是取max(maxx, 4)
反之
k的最大值就是max(maxx, 2)
2.如果pow(powl(m, 1.0 / 3), 3) == m
那么k的最大值就是取max(maxx, 3)
3.最后k的最大值就是去max(maxx, 0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = (int) 1e4 + 100;
int num[maxn];
int prime[maxn];
int e;
void init() {
for (int i = 2; i <= 10000; i++) {
if (!num[i]) {
if (i > 10000 / i) {
continue;
}
for (int j = i * i; j < 10000; j += i) {
num[j] = 1;
}
}
}
}
void init_prime() {
e = 0;
init();
for (int i = 2; i <= 10000; i++) {
if (!num[i]) {
prime[e++] = i;
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init_prime();
int T;
cin >> T;
while (T--) {
ll n;
cin >> n;
int minn = 100;
for (int i = 0; i < e; i++) {
if(n % prime[i] == 0){
int ans = 0;
while(n % prime[i] == 0){
ans++;
n /= prime[i];
}
minn = min(ans, minn);
}
if(n == 1 || minn == 1){
break;
}
}
if(n == 1 || minn == 1){
cout << minn << endl;
}else{
int flag = 0;
ll four = powl(n, 0.25) + 0.5;
if(four * four * four * four == n){
minn = min(minn, 4);
flag = 1;
}else {
ll two = powl(n, 0.5) + 0.5;
if(two * two == n){
minn = min(minn, 2);
flag = 1;
}
}
ll three = powl(n, 1.0 / 3) + 0.5;
if(three * three * three == n){
minn = min(minn, 3);
flag = 1;
}
if(flag == 0){
cout << 1 << endl;
}else{
cout << minn << endl;
}
}
}
}