【大整数筛】立方数

约定不等于承诺〃 2024-03-24 09:35 73阅读 0赞

**根本不会**

**最大的收获就是，对于一个大数(>1e8的数)，一般要去考虑唯一分解**

[1008-立方数\_2021秋季算法入门班第十章习题：数学 (nowcoder.com)][1008-_2021_ _nowcoder.com]

题意：

![0967a883205d4e4a9e55e2e9f12e327d.png][]

思路：

这道题首先看数据范围1e18

就算是质因子分解复杂度也不行

考虑把3e5以下的质因子全部筛去，对于那些幂次>3且%3==0的，需要算贡献

然后考虑被筛掉之后的n，剩下的质因子都是大于3e5的，所以质因子个数不含超过3个，所以如果还去计算贡献的话只有一种情况：p\*p\*p==n

因此二分把其立方根二分出来，如果存在立方根就算贡献，没有就不算

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    using i64 = long long;
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    int n,len=0,ans=1;
    int prime[mxn],vis[mxn];
    void p_init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;i<=n/prime[j];j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    void solve(){
        cin>>n;
        int A=1;
        for(int i=1;i<=len;i++){
            int p=prime[i];
            if(n%p==0){
                int s=0;
                while(n%p==0){
                    n/=p;
                    s++;
                    if(s%3==0) A*=p;
                }
            }
        }
        int l=1,r=1e6;
        int ans=1;
        while(l<=r){
            int mid=l+r>>1;
            if(mid*mid*mid==n){
                ans=mid;
                break;
            }
            if(mid*mid*mid>n) r=mid-1;
            else l=mid+1;
        }
        A*=ans;
        cout<<A<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        p_init(1e5);
        while(__--)solve();return 0;
    }

[1008-_2021_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/26656/1008
[0967a883205d4e4a9e55e2e9f12e327d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/feb937099498448caab4eda1f0d60085.png