立方数
题意
对于给定的正整数 N，求最大的正整数 A，使得存在正整数 B，满足 A^3×B=N
输入包含 T 组数据，1≤T≤10,000；1≤N≤10^18
考虑直接一些的做法 尝试对每个N作质因数分解，经简单的统计可得出答案，复杂度O(TN^(1/2)) 我们先做简单一点的优化，容易发现其实只要枚举10^ 6(N^ (1/3)以内)的质数就好，复杂度O(TN^ (1/3)/ln(N ^(1/3) ) ) 再作进一步的分析，如果我们仅使用N^(1/4)(记为W)以内的质数去试除，那么最后余下的数X仅具有大于W的因子 此时X要么是一个完全立方数，要么对答案没有任何贡献，只需要使用二分法来验证X是不是一个完全立方数即可
为什么最后余下的数x一定要么是一个完全立方数要么对答案没有贡献
即为什么剩下的不会有 x=p1^3 × p2^2 首先经过用N^(1/4)(记为W)以内的质数去试除 p1^4>x , 如果p1^3 < x
已知 p1<p2那么 p1^3 × p2^m必定>x
所以剩下的x要么是完全立方数要么x=p1^ n1×…pm^ ni; ni一定小于3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| # include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(int)1e5+5;
ll prime[maxn];
bool vis[maxn];
void intn(){
int cnt=0;
for(ll i=2;i<=maxn;i++){
if(!vis[i])prime[cnt++]=i;
for(ll j=0;j<cnt&&prime[j]*i<=maxn;j++){
vis[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}
int main(){
intn();
int t;scanf("%d",&t);
while(t--){
ll n;
scanf("%lld",&n);
ll ans=1;
for(ll i=0;prime[i]*prime[i]*prime[i]*prime[i]<=n;i++){
ll tr=prime[i]*prime[i]*prime[i];
while(n%tr==0){
n/=tr;
ans*=prime[i];
}
while(n%prime[i]==0)n/=prime[i];
}
int lb = 1, rb = 1000000;
while(lb <= rb){
int md = lb + rb >> 1;
if((ll)md * md * md < n)
lb = md + 1;
else
rb = md - 1;
}
if((ll)lb * lb * lb == n)ans *= lb;
printf("%lld\n",ans);
}
}
|