Why?大佬求调。

CPP

#include <bits/stdc++.h>
using namespace std ;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define lowbit(x) (x&(-x))
#define int long long
#define double long double
const int N = 5e5 + 9  ;
const int inf = 1e18 ;
const int mod = 998244353 ;
int n , k ;
int t ;
signed main ( ){
    IOS ;
    cin >> t ;
    while ( t-- ){
        cin >> n >> k ;
        double n2 = sqrtl ( n ) ;
        int m = pow ( n2 , (double)1 / (double) k ) ;
        int ans ;
        if ( pow ( (int)pow ( n , (double) 1 / (double) k ) , k ) == n ){
            cout << (int)pow ( n , (double) 1 / (double) k ) << "\n" ;
            continue ;
        }
        for ( int i = m + 10  ; i >= 1 ; --i ){
            int w = pow ( i , k ) ;
            if ( n % w == 0 ){
                ans = i ;
                break ;
            }
        }
        cout << ans << "\n" ;
    }
    return 0 ;
}

应该是

O(Tn^{1/6})

的。

大致思路：因为

n

的因数应该是

\geq \sqrt{n}

的，当然除了

n

本身。

所以，我先枚举

p^k \leq \sqrt n

的

p \in [ 1 , \sqrt [k]{n} ]

。判断

p^k

是否可以整除

n

。当然，我会特判掉

p^k=n

的情况。

没有TLE，只对了3个点，其他均WA。link

不知道是精度不够，还是没有考虑到特殊情况……

大佬求调。

讨论操作

回复

相关推荐

Why?大佬求调。