题意
(T) 次询问，每次给一个正整数 (x)，问最大的整数 (a) 满足 (a^3b=x)，其中 (b) 是正整数。
题解
我想了一个 (O(Tx^{0.25})) 的根号分治做法，成功被卡常。
这是正解：
有一个奇妙的性质：把 (x) 中所有 (le x^{0.25}) 的质因子都去掉，剩下的数要不然是一个完全立方数，要不然其中所有质因子的次数都小于 (3)。
证明：假如剩下的部分能被表示成 (k^3y) 的形式（(k,y>1)），因为已经去掉了所有 (le x^{0.25}) 的质因子，所以 (k,y>x^{0.25})，所以 (k^3y>x)，矛盾。
所以我们筛出 ((10^{18})^{0.25}) 以内的所有质数，再预处理 (1sim 10^{18}) 内的所有完全立方数，就能过了。
不会分析时间复杂度。。。感觉挺奇妙的，时间复杂度应该和根号分治做法一样，但根号分治就是过不了。
代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <unordered_map>
#include <cmath>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T> void Read(T &x){
x=0;int _f=1;
char ch=getchar();
while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
x=x*_f;
}
template<typename T,typename... Args> void Read(T &x,Args& ...others){
Read(x);Read(others...);
}
typedef long long ll;
const int Inf=0x3f3f3f3f,Q=31655,CBRT=1e6+5;
int prime[Q],prCnt=0,vis[Q];
void Sieve(int mx){
vis[1]=1;
For(i,2,mx){
if(!vis[i]) prime[++prCnt]=i;
for(int j=1;j<=prCnt&&1LL*i*prime[j]<=mx;++j){
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
unordered_map<ll,ll> mp;
int T;
int main(){
Sieve(Q-1);
for(ll i=1;i<CBRT;++i) mp.insert({i*i*i,i});
Read(T);
while(T--){
ll x,ans=1;Read(x);
for(int j=1;j<=prCnt;++j){
int cnt=0;
while(x%prime[j]==0){
++cnt,x/=prime[j];
if(cnt>=3) ans*=prime[j],cnt-=3;
}
}
if(mp.count(x)) ans*=mp[x];
printf("%lld
",ans);
}
return 0;
}