中国商标网商标查询官方网站,网站栏目类型,网站配色 蓝色,网站访问很慢Problem Description
著名出题人小Q出过非常多的题目#xff0c;在这个漫长的过程中他发现#xff0c;确定题目的数据范围是非常痛苦的一件事。 每当思考完一道题目的时间效率#xff0c;小Q就需要结合时限以及评测机配置来设置合理的数据范围。 因为确定数据范围是一件痛苦…Problem Description
著名出题人小Q出过非常多的题目在这个漫长的过程中他发现确定题目的数据范围是非常痛苦的一件事。 每当思考完一道题目的时间效率小Q就需要结合时限以及评测机配置来设置合理的数据范围。 因为确定数据范围是一件痛苦的事小Q出了非常多的题目之后都没有它们设置数据范围。对于一道题目小Q会告诉你他的算法的时间复杂度为O(nalogbn)且蕴含在这个大O记号下的常数为1。同时小Q还会告诉你评测机在规定时限内可以执行k条指令。小Q认为只要na(⌈log2n⌉)b不超过k那么就是合理的数据范围。其中⌈x⌉表示最小的不小于x的正整数即x上取整。 自然小Q希望题目的数据范围n越大越好他希望你写一个程序帮助他设置最大的数据范围。
Input
第一行包含一个正整数T(1≤T≤1000)表示测试数据的组数。 每组数据包含一行三个正整数a,b,k(1≤a,b≤10,106≤k≤1018)分别描述时间复杂度以及允许的指令数。
Output
对于每组数据输出一行一个正整数n即最大可能的n。
Sample Input
3
1 1 100000000
2 1 100000000
1 3 200000000 Sample Output
4347826
2886
48828
解析
首先二分枚举n很容易想到但check函数如果像题目一样去做就会爆掉肯定不能像题目所说的那样去做不可能白送分
所以我们要想一个另外的方式句验证这就要靠思维和数感了
将乘法变成除法且用正整型存储n^a就是n自乘a次n自乘a次等于k那么k除n除a次等于1
#includeiostream
#includecstdio
#includecstdlib
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemap
using namespace std;
typedef long long LL;
LL a, b, k,ppp;int check(LL m) {LL kk k;for (int i 1; i a; i) {if (kk / m 0) {kk / m;}elsereturn 1;}LL t1 ceil(log2(m));if (t1 0)return 0;for (int i 1; i b; i) {if (kk / t1 0)kk / t1;elsereturn 1;}return 0;
}int main() {int T;scanf(%d, T);while (T--) {scanf(%lld%lld%lld, a, b, k);LL l 1, r k, mid, ans; while (l r) {mid l (r - l) / 2;if (check(mid)) {r mid - 1;}else {ans mid;l mid 1;}}printf(%lld\n, ans);}return 0;
}
