2020牛客寒假训练营Day6 - E 立方数

传送门：2020牛客寒假训练营Day6 - E

题目描述

对于给定的正整数N，求最大的正整数A，使得存在正整数B，满足$A^3*B=N$
输入包含T组数据，$1≤T≤10000$,$1≤N≤10^18$

输入描述

第一行数字T表示数据组数
接下来一行，T个整数N

输出描述

T行，每一行一个数字表示答案

思路分析

因为是立方，所以很容易想到找$10^6$以下的素数，但是这样还是会TLE
再进一步分析，如果仅使用$N^{1/4}$（记为W），以为的素数试除，那么最后余下的的数X肯定只有大于W的因子
要么他是立方数，要么他对答案没有贡献，我们可以用二分的办法判断它是不是立方数

样例输入

4
27 24 7 54

样例输出

3
2
1
3

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
 
using namespace std;
 
const int INF = 0x3f3f3f3f;
const int N=1e6+10;
 
ll prim[N],cnt;
ll sq[N],ssq[N];
bool ok[N];
 
void init() {
    mem(ok,1);
    for(ll i=2; i<100000; i++) {
        if(ok[i]) {
            prim[++cnt]=i;
            sq[i]=i*i*i;
            ssq[i]=i*i*i*i;
            for(ll j=i*i; j<100000; j+=i)
                ok[j]=0;
        }
    }
}
 
int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
 
 
    init();
    int t;
    cin>>t;
    while(t--) {
        ll n;
        cin>>n;
        ll ans=1;
        for(int i=1; ssq[prim[i]]<=n; i++) {
            if(n%prim[i]==0) {
                while(n % sq[prim[i]]==0) {
                    ans*=prim[i];
                    n/=sq[prim[i]];
                }
                while(n%prim[i]==0)
                    n/=prim[i];
            }
        }
        ll l=1,r=1000000;
        while(r>=l){
            ll mid=l+r>>1;
            if(mid*mid*mid==n){
                ans*=mid;
                break;
            }
            if(mid*mid*mid>n){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        cout<<ans<<endl;
         
    }
 
 
 
 
 
    return 0;
}