题面
T
≤
50
000
T\leq50\,000
T≤50000 组数据：
输入一个数
N
N
N （
2
≤
N
≤
1
0
18
2\leq N\leq 10^{18}
2≤N≤1018）,输出一个数，表示
N
N
N 质因数分解后，每个质因数的幂的最小值。
题解
妙妙题！
一种神奇的做法：
我们把
N
5
<
3
982
\sqrt[5]{N}<3\,982
5N
<3982 以内的质数都筛出来，以便把
N
N
N 的
≤
N
5
\leq\sqrt[5]{N}
≤5N
的质因数都找到，统计次数，处理答案。然后把
N
N
N 里面的这些质因子全部除掉。这一步的时间大概在 500 左右。
用反证法，不难证明剩下的
N
N
N 最多只有 4 个质因数，所以，要么存在质因数的幂为 1 （答案输出 1），如果不存在，要么是某个质数的平方，要么是三次方、四次方，这三者都可以求出
N
2
,
N
3
,
N
4
\sqrt[2]{N}~,~\sqrt[3]{N}~,~\sqrt[4]{N}
2N
, 3N
, 4N
然后
O
(
1
)
O(1)
O(1) 判断。
CODE
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 10005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
int n,m,i,j,s,o,k;
int MOD = 1;
inline LL safemul(LL a,LL b,LL MOD) {
return a*b%MOD;
// LL nm = a*b-((LL)((long DB)a/MOD*b+0.5)*MOD);
// return (nm%MOD+MOD)%MOD;
}
LL qkpow(LL a,LL b,LL MOD) {
LL res = 1;
while(b > 0) {
if(b & 1) {
if(res*a >= MOD) res = safemul(res,a,MOD)+MOD;
else res = safemul(res,a,MOD);
}
if(a * a >= MOD) a = safemul(a,a,MOD)+MOD;
else a = safemul(a,a,MOD);
b >>= 1;
}return res;
}
LL L;
LL PHI(LL x) {
LL as = x;
for(int i = 2;i *1ll* i <= x;i ++) {
if(x % i == 0) {
as = as/i*(i-1);
while(x % i == 0) x /= i;
}
}
if(x > 1) as = as / x * (x-1);
return as;
}
bool comp(LL a,LL b,LL c) {
LL res = 1;
for(int i = 1;i <= b;i ++) {
if(res > c/a) return 1;
res = res * a;
}return res > c;
}
int p[MAXN],cnt;
bool f[MAXN];
void sieve(int n) {
for(int i = 2;i <= n;i ++) {
if(!f[i]) p[++ cnt] = i;
for(int j = 1;j <= cnt && i*p[j] <= n;j ++) {
f[i*p[j]] = 1;
if(i%p[j] == 0) break;
}
}return ;
}
int depcheck(int tm,LL &MOD) {
int ans = 64;
for(int ii = 1;ii <= cnt;ii ++) {
int i = p[ii];
if(MOD % i == 0) {
int ct = 0;
while(MOD % i == 0) MOD /= i,ct ++;
ans = min(ans,ct);
}
}
return ans;
}
int main() {
sieve(4000);
int T = read();
while(T --) {
LL N = read();
int as = depcheck(5,N);
LL y4 = (LL)(pow((DB)N,0.25)+0.1);
LL y3 = (LL)(pow((DB)N,1.0/3.0)+0.1);
LL y2 = (LL)(sqrt((DB)N)+0.1);
if(N > 1) {
if(y4*y4*y4*y4 == N) as = min(as,4);
else if(y3*y3*y3 == N) as = min(as,3);
else if(y2*y2 == N) as = min(as,2);
else as = 1;
}
printf("%d\n",as);
}
return 0;
}
