E 立方数

链接：https://ac.nowcoder.com/acm/contest/3007/E

对于给定的正整数 N，求最大的正整数 A，使得存在正整数 B，满足 A3B=N

输入包含 T 组数据，1≤T≤10,000；1≤N≤1018

输入描述:

第一行数字 T 表示数据组数

接下来一行，T 个正整数 N

输出描述:

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

示例1

输入

复制

4
27 24 7 54

输出

复制

3
2
1
3

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,t;
long long a[1000001],b[1000001],c[1000001];
map<long long,long long>m;
int main()
{
	int j=0;
	for(int i=2;i<=31700;i++)//还说不是卡常！！！ 
	{
		if(m[i]==0)
		{
			j++;
			a[j]=(long long)i*i*i;
			c[j]=(long long)i*i*i*i;//虽然不知道为什么 
			b[j]=i;
			//cout<<c[j]<<endl;
			for(int k=i*2;k<=31700;k+=i)
			{
				m[k]++;
			}
		}
	}
    scanf("%lld",&t);
    while(t--)
    {
    	scanf("%lld",&n);
    	int ans=1;
    	//l=(long long)pow(n,1.0/3);
    	for(int i=1;c[i]<=n&&i<=j;i++)
    	{
    		if(n%b[i]==0)
    		{
    			while(n%a[i]==0)
    			{
    				n/=a[i];
    				ans*=b[i];
    			}
    			while(n%b[i]==0)
    			{
    				n/=b[i];
    			}
    		}
    	}
		long long l=1,r=1000000;
        while(l<=r)
		{
            long long mid=(l+r)/2;
            if(mid*mid*mid<n)
            l=mid+1;
            else
            r=mid-1;
        }
        if(l*l*l==n)
    	ans*=l;
    	printf("%d\n",ans);
    }
}