自动搬运

查看原文

来自洛谷，原作者为

	hongzy **

搬运于2025-08-24 22:00:15，当前版本为作者最后更新于2018-04-21 19:21:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

数论 + 二分

首先，这里有一个结论：若把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;
}