B - 缺失的数据范围

著名出题人小Q出过非常多的题目，在这个漫长的过程中他发现，确定题目的数据范围是非常痛苦的一件事。

每当思考完一道题目的时间效率，小Q就需要结合时限以及评测机配置来设置合理的数据范围。

因为确定数据范围是一件痛苦的事，小Q出了非常多的题目之后，都没有它们设置数据范围。对于一道题目，小Q会告诉你他的算法的时间复杂度为O(n^a\log^bn)O(nalogbn)，且蕴含在这个大OO记号下的常数为11。同时，小Q还会告诉你评测机在规定时限内可以执行kk条指令。小Q认为只要n^a\left(\lceil\log_2n\rceil\right)^bna(⌈log2​n⌉)b不超过kk，那么就是合理的数据范围。其中，\lceil x\rceil⌈x⌉表示最小的不小于xx的正整数，即xx上取整。

自然，小Q希望题目的数据范围nn越大越好，他希望你写一个程序帮助他设置最大的数据范围。

Input

第一行包含一个正整数T(1\leq T\leq 1000)T(1≤T≤1000)，表示测试数据的组数。

每组数据包含一行三个正整数a,b,k(1\leq a,b\leq 10,10^6\leq k\leq 10^{18})a,b,k(1≤a,b≤10,106≤k≤1018)，分别描述时间复杂度以及允许的指令数。

Output

对于每组数据，输出一行一个正整数nn，即最大可能的nn。

Sample

3 1 1 100000000 2 1 100000000 1 3 200000000

4347826 2886 48828

 思路：二分n

注意log2不能使用longlong，需要手写log2

ll log(ll x){
	ll con=0;
	ll ans=1;
	while(ans<x){
		con++;
		ans*=2;
	}
	return con;
}

然后因为n^a会爆longlong，那么我们就用__int128存数

乘a个n再乘b个log（n），每乘一下判断是不是小于k即可

bool cheek(ll n){
	__int128 ans=1;
	for(int i=0;i<a;i++){
		ans*=n;
		if(ans>k)return false;
	}
	ll op=log(n);
	for(int i=0;i<b;i++){
		ans*=op;
		if(ans>k)return false;
	}
	return true;
}

 接下来是完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,k;
ll log(ll x){
	ll con=0;
	ll ans=1;
	while(ans<x){
		con++;
		ans*=2;
	}
	return con;
}
bool cheek(ll n){
	__int128 ans=1;
	for(int i=0;i<a;i++){
		ans*=n;
		if(ans>k)return false;
	}
	ll op=log(n);
	for(int i=0;i<b;i++){
		ans*=op;
		if(ans>k)return false;
	}
	return true;
}
void sove(){
	scanf("%lld%lld%lld",&a,&b,&k);
	ll l=0,r=1e18;
	while(l<r){
		ll mid=(l+r+1)/2;
	//	cout<<"mid=="<<mid<<endl;
		if(cheek(mid))l=mid;
		else r=mid-1;
	//	cout<<"l=="<<l<<" r=="<<r<<endl;
	}
	printf("%lld\n",l);	
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		sove();
	}
	
	return 0;
}