[数据结构与算法]立方数 (欧拉筛 思维

添加链接描述
根据算数基本定理 将素数得到 因为是n是1e18
可以想到n^(1/3)为1e6 但时间复杂度还是T*o(n^(1/3)会超时
可以优化到n^(1/4) 然后最后判断a * a *a是否可以等于n

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int N=40009;
ll vis[N],p[N],cnt=0;
void euler(ll n){
    for(int i=2;i<=n;i++){
        if(vis[i]==0){
            vis[i]=i;
            p[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            if(i*p[j]>n||p[j]>vis[i])break;
            vis[p[j]*i]=p[j];
        }
    }
}
ll solve(ll n){
    ll ans=1,tot=0;
    for(int i=1;i<=cnt;i++){
        if(p[i]>n)break;
        if(n%p[i]==0){
            tot=0;
            while(n%p[i]==0){
                tot++;
                if(tot==3){
                    ans*=p[i];
                    tot=0; //这个很关键 满足条件就是*=ans
                }
                n/=p[i];
            }
        }
    }
    if(n!=1){
        ll a=ceill(pow(n,1.0/3));//开根号三次方判断是否有常数
        if(a*a*a==n)ans*=a;
    }
    return ans;
}
signed main(){
    euler(40005);
    int T;
    scanf("%lld",&T);
    while(T--){
        ll n;
        scanf("%lld",&n);
        printf("%lld\n",solve(n));
    }
    return 0;
}