二分题

我最喜欢二分啦！！！

时间复杂度为 $O(Qlog^2N)$ 。

#include<bits/stdc++.h>
using namespace std;
#define int __int128
const int INF=(int)1<<64;
template<typename T>inline void qr(T &x){
	int f=1;x=0;
	char c=getchar();
	for(;!isdigit(c);c=getchar())f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-'0';
	x*=f;
}
template<typename T>inline void qw(T x){
	if(x<0)
		putchar('-'),x=-x;
	if(x/10)qw(x/10);
	putchar(x%10+'0');
}
inline int qpow(int a,int b){
	int res=1;
	for(;b;b>>=1,a*=a){
		if(b&1)
			res*=a;
		if(a>=INF||res>=INF)
			return INF;
	}
	return res;
}
int a,k;//AK CSP-J/S
signed main(){
	int Q;
	qr(Q);
	while(Q--){
		qr(a);qr(k);
		int L=0,R=INF;
		while(L+1<R){
			int M=L+R>>1;
			if(qpow(M,k)<=a)L=M;
			else R=M;
		}
		qw(L);
		puts("");
	} 
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define LL __int128
template<typename T>void qr(T& x)
{
	x=0;int f=1;char c=getchar();
	for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c);c=getchar())x=x*10+c-48;
	x=x*f;
}
template<typename T>void qw(T x)
{
	if(x<0)x=-x,putchar('-');
	if(x/10)qw(x/10);
	putchar(x%10+48); 
}
bool check(LL x,int k,LL m)
{
	LL ans=1;
	for(int i=1;i<=k;i++)
	{
		ans*=x;
		if(ans>m)return 0;
	}
	return 1;
}
void solve()
{
	LL x,k;qr(x),qr(k);
	if(k==1){qw(x);puts("");return;}
	LL l=0,r=(1ll<<62),ans=0;
	while(l<=r)
	{
		LL mid=(l+r)>>1;
		if(check(mid,k,x))l=mid+1,ans=mid;
		else r=mid-1;
	}
	qw(ans);puts("");
}
signed main()
{
	int t;cin>>t;
	while(t--)solve();
	return 0;
}