题目链接:
乍一看还以为是Pollard_rho算法,其实大可不必。
发现\(1<= n <= 1e18\),我们可以将n分为两部分(分块思想降低时间复杂度)。
剔除小于等于\(4000\)的所有质因子,剩余的设为x,设此时得到的答案为\(minnum\)
如果x为\(1\),那我们得到答案,可以直接返回
否则知道x的质因子一定大于\(4000\),可以分类讨论
若x可写成\(x=p^{(1/4)}\),\(minnum = min(minnum,4)\),返回
若x可写成\(x=p^{(1/3)}\),\(minnum = min(minnum,3)\),返回
否则x若可写成平方的形式,\(minnum = min(minnum,2)\),注意要区分为4的情况
否则我们知道\(minnum\)一定为\(1\)
时间复杂度大约为\(O(t) * 1000\)
(将大问题化为小问题然后分类讨论)
代码:
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 10001;
int prime[N], flag[N], tot, t;
LL n;
LL mulfou(LL x) { return x*x*x*x; }
LL multhe(LL x) { return x*x*x; }
void get_prime(int n)
{
for(int i = 2;i <= n; i++)
{
if(!flag[i]) prime[++ tot] = i;
for(int j = 1;j <= tot && i * prime[j] <= n; j++)
{
flag[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
}
void work(LL n)
{
if(n == 1) { printf("0\n");return; }
int minnum = 100; LL x = n;
for(int i = 1;i <= tot; i++)
{
if(x % (LL) prime[i] != 0) continue;
int res = 0;
while(x % prime[i] == 0) ++ res,x /= prime[i];
minnum = min(minnum,res);
}
if(x == 1) {printf("%d\n",minnum);return;}
if(minnum == 1) {printf("1\n");return;}
LL sqr = pow(x,1.0/4.0), sqr2 = pow(x,1.0/2.0);
if(mulfou(sqr) == x || mulfou(sqr + 1) == x || mulfou(sqr - 1) == x)
{ minnum = min(minnum,4);printf("%d\n",minnum); return; }
else if(sqr2 * sqr2 == x) { minnum = min(minnum,2);printf("%d\n",minnum);return; }
else
{
LL sqr3 = (LL)pow(1.0*x,1.0/3.0);
if(multhe(sqr3) == x || multhe(sqr3 + 1) == x || multhe(sqr3 - 1) == x)
{ minnum = min(3,minnum);printf("%d\n",minnum); return; }
else { printf("1\n"); return; }
}
}
int main()
{
get_prime(4000);
scanf("%d",&t);
while(t --)
{
scanf("%lld",&n);
work(n);
}
}
/*
1
512384096008
*/