题解 P4446 【[AHOI2018初中组]根式化简】

· · 题解

数论 + 二分

首先，这里有一个结论：若把x^(1/4)以内的素因子全部筛(除)掉，则剩下的这个x一定是一个完全立方数或不可化简(开立方)的数.

证明：若还存在因子p>x^(1/4)，使得剩下的x能可以表示成b*(p^3)，那这里的b一定>x^(1/4)（之前已经筛了x^(1/4)以内素因子）。那么b*(p^3)会大于x，因此不存在p。不过有个特殊情况，就是b=1，p^3=x，即x是完全立方数.

算法过程：

  1. 取x的最大值10^18，(10^18)^(1/4)大约为31650，预处理出31650以内素数
  2. 筛掉x^(1/4)以内的素因子，同时记得如果出现可以开立方要累乘答案.
  3. 最后查看筛完以后的x是不是p^3.可以预处理出来1~x^(1/3)的立方表，然后用STL二分函数lower_bound查找.
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long LL;
const int n = 31650, m = 1000000; //n为x^(1/4)的上限，m为x^(1/3)的上限 

LL pow3[m + 10];      //每个数的立方 
int plist[3510], cnt; //素数表 

bool p[40010]; 
void prime() {        //埃氏筛法 
    int sq = sqrt(n) + 0.5;
    for(int i=2; i<=n; i++) p[i] = true;
    p[1] = false;
    for(int i=2; i<=sq; i++) if(p[i])
        for(int j=i*i; j<=n; j+=i) p[j] = false;
    for(int i=1; i<=n; i++) if(p[i]) plist[++ cnt] = i;
}

int main() {
    prime(); //预处理素数 
    for(LL i=1; i<=m; i++) pow3[i] = i*i*i; //预处理立方表 
    int T; LL x; 
    scanf("%d", &T);
    while(T --) {
        LL ans = 1, c;
        scanf("%lld", &x);
        for(int i=1; i<=cnt && plist[i] <= x; i++) {
            c = 0;  //记录此素因子的出现次数 
            while(x % plist[i] == 0) { //此素数是因子 
                c ++; x /= plist[i];
                if(c == 3) ans *= plist[i], c = 0; //每次出现素因子立方就累积到答案 
            }
        }
        LL k = lower_bound(pow3+1, pow3+m+1, x) - pow3; //查看剩下的x是不是立方 
        printf("%lld\n", ans*(k*k*k == x ? k : 1)); 
    }
    return 0;
}