1008 立方数 素数筛求约数 stl黑科技 二分 数论

本文主要是介绍1008 立方数 素数筛求约数 stl黑科技 二分 数论，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

分析

首度。我开vector，开map 都是tle，改成数组和cnt 计数就对了。

//-------------------------代码----------------------------

#define int ll
const int N = 1e5+10;
int n,m,primes[N],cnt;
bool st[N];

int qmi(int a,int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a;
        a = a * a ;
        b >>= 1;
    }return res;
}

void solve()
{
    cin>>n;
    map<int,int> mp;
    int ans = 1;
    for(int i = 0;i<cnt;i++) {
        if(n % primes[i] == 0) {
            int cnt = 0;
            while(n % primes[i] == 0) {
                n /= primes[i];
                cnt ++ ;
                if(cnt % 3 == 0) {
                    ans *= primes[i];
                }
            }
        }
    }
    
    int l = 1e5,r = 1e6;
    while( l < r) {
        int mid = l + r  >> 1;
        if(mid * mid * mid == n) {
            ans *= mid;
            break;
        } else if( mid * mid * mid >= n) {
            r = mid;
        } else l = mid + 1;
    }
    cout<<ans<<endl;
}
void get_prime() {
    for(int i = 2;i<=N;i++) {
        if(!st[i]) primes[cnt ++ ] = i;
        for(int j = 0;j < cnt && primes[j] * i <= N;j++) {
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}
signed main(){
    clapping();TLE;
    get_prime();
    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

这篇关于1008 立方数 素数筛求约数 stl黑科技 二分 数论的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！