2020牛客寒假算法基础集训营6 E-立方数

2020牛客寒假算法基础集训营6 E-立方数 - 质因子分解

357 浏览 0 回复 2020-02-17

工大最菜

+关注

题目链接：https://ac.nowcoder.com/acm/contest/3007/E
题目大意：

我们要求最大的A。
我们根据唯一分解定理：
$N = e_{1}^{p_{1}} * e_{2}^{p_{2}} * e_{2}^{p_{2}} * e_{2}^{p_{2}} * . . . e_{k}^{p_{k}}$
那么
$如果 p i % 3 = = 0 那么 A * = e_{i} * (p i / 3)$
现在我们就是要 $枚举 e i 来得到 A$
我们发现 $e_{i} 的最大值为 N^{1 / 3}$
我们枚举 $N^{1 / 3} 里的素数那么复杂度是 O (T N^{(1 / 3)} / l n (N^{(1 / 3)}))$
我们可以进一步优化： $如果枚举到 N^{1 / 4}, 那么我们把 N 在 N^{1 / 4} 里的素数全部筛出后得到 X$
$那么 X 的形式为 e^{p} * B, 并且 e, B > N^{1 / 4} ，那么可以知道： p < 4 。如果 p > = 4 那么 e^{p} * B > N$
$\begin{matrix} <mstyle displaystyle="false" scriptlevel="0"> 1 : p = 3 那么 B 一定等于 1 证明 N^{3 / 4} * B, 而且 B > N^{1 / 4} 那么 N^{3 / 4} * B > N 不可能, 所以 B = 1 </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> 2 : p < 3 那么 e i 对结果没有贡献 </mstyle> \end{matrix}$
$所以我们枚举 N^{1 / 4} 的素数, 再判断 X 是否为立方数，复杂度 : O (T N^{(1 / 4)} / l n (N^{(1 / 4)}))$

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
#define MAXN 1000005
#define MAXL 5299710
LL prime[MAXN];
LL Lf[MAXN];//存储立方
LL check[MAXL];
LL tot = 0;
void get_prime(LL n){
    memset(check, 0, sizeof(check));
    for(LL i = 2; i <= n; ++i){
      if (!check[i])
        prime[tot++] = i, Lf[tot-1]=i*i*i;
 
      for (LL j = 0; j < tot; ++j){
        if (i * prime[j] > n)
          break;
 
        check[i*prime[j]] = 1;
        if (i % prime[j] == 0)
          break;
      }
    }
}
 
int main(){
 
    get_prime(31622);
    int t;scanf("%d", &t);
    while(t--){
        LL n, A=1;scanf("%lld", &n);
        for(int i=0; i<tot&&prime[i]<=n; i++){
            while(n%Lf[i]==0){//立方筛完
                A*=prime[i];
                n/=Lf[i];
            }
            while(n%prime[i]==0){
                n/=prime[i];
            }
        }
 
        int lb = 1, rb = 1000000;//二分判断X是不是立方数
        while(lb <= rb){
            int md = lb + rb >> 1;
            if((LL)md * md * md < n)
                lb = md + 1;
            else
                rb = md - 1;
        }
        if((LL)lb * lb * lb == n)
            A *= lb;
        printf("%lld\n", A);
    }
 
    return 0;
}