Time limit 1000 ms
Memory limit 65536 kB
OS Windows
中文题意
给一个数n，设将n质因数分解后可以得到
其中(omega(n))意思是n的不同质因子个数，(a_i)是n的质因子。
要求输出最小的(p_i)。
题解
看完题解感觉很妙啊——
Let's first factorize (N) using prime numbers not larger than (N^{frac{1}{5}}). And let's denote (M) as the left part, all the prime factors of (M) are larger than (N^{frac{1}{5}}). If (M=1) then we are done, otherwise M can only be (P^2), (P^3), (P^4) or (P^2 imes Q^2), here (P) and (Q) are prime numbers.
- If (M^{frac{1}{4}}) is an integer, we can know that (M=P^4). Update answer using 4 and return.
- If (M^{frac{1}{3}}) is an integer, we can know that (M=P^3). Update answer using 3 and return.
- If (M^{frac{1}{2}}) is an integer, we can know that (M=P^2) or (M=P^2 imes Q^2). No matter which situation, we can always update answer using 2 and return.
- If (1)(2)(3) are false, we can know that answer=1.
Since there are just (O(frac{N^{frac{1}{5}}}{log(N)})) prime numbers, so the expected running time is (O(frac{TN^{frac{1}{5}}}{log(N)})).
官方题解导致我一开始没反应过来的地方在于
M can only be (P^2), (P^3), (P^4) or (P^2 imes Q^2),
不是only，(M)还可以是(PQRS)、(P^2QR)、(PQR)、(P^3Q)、(P^2Q)，之类的，而这些的答案都是1，也就是题解里编号4所说的，不是前三种情况。
另外一个问题，如何判断(sqrt[4]M)、(sqrt[3]M)、(sqrt{M})是否是整数呢？我们可以求出(sqrt[4]M)、(sqrt[3]M)、(sqrt{M})向下取整后的结果，再乘回去，比如，看看是否存在(lfloorsqrt{M} floor^2==M)。
还有，求(lfloorsqrt[3]{M}
floor)时，pow函数精度不太够，用pow(n,1.0/3.0)会WA，要二分法求。下面这段二分法的代码来自这个博客代码里的two函数，要是有整数解就返回整数解，否则返回负一，这倒是挺好。
还有……复杂度那个log哪里来的？和质数分布有关？
源代码
#include<stdio.h>
#include<math.h>
#include<algorithm>
int T;
long long n;
long long cnt=0;
long long prime[10000];
long long ans;
bool vis[10000];
void shai()//取变量名一次回到解放前。还别说，挺方便的，一目了然
{
for(int i=2;i<=10000;i++)
{
if(!vis[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=10000;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
}
long long sancigeng(long long a)
{
long long l=1,r=(long long)pow(n*1.0, 1.0 / 3) + 1,mid;
while(l<=r){
mid=(l+r)>>1;
if(mid*mid*mid==n) return mid;
else if(mid*mid*mid>n) r=mid-1;
else l=mid+1;
}
return -1;
}
int main()
{
shai();
//freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
ans=0x7fffffff;
int pw,pr;
for(int i=1;i<=cnt;i++)
{
if(n%prime[i]==0)
{
pr=prime[i],pw=0;
while(n%pr==0)
{
n/=pr;
pw++;
}
if(pw<ans) ans=pw;
}
if(ans==1)
{
n=1;
break;
}
}
if(n==1)
{
printf("%lld
",ans);
continue;
}
long long temp1=sqrt(n),temp2=sqrt(temp1),temp3=sancigeng(n);
if(temp2*temp2==temp1&&temp1*temp1==n)
{//algorithm里的max和min不支持long long和int混杂的参数，居然不会隐式类型转换
ans=std::min(ans,4LL);
}
else if(temp3>=0)
{
ans=std::min(ans,3LL);
}
else if(temp1*temp1==n)
{
ans=std::min(ans,2LL);
}
else ans=1;
printf("%lld
",ans);
}
return 0;
}