链接: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);
}
}