2017年浙江中医药大学大学生程序设计竞赛（重现赛）B - 一生之敌
题目描述
大家都知道Alice和Bob两个人是一生之敌。(雾 但某天，他们两个人发了疯。想知道他们两个是否可以成为朋友。于是他们做了一个令人窒息的决定。
Alice和Bob每个人任意选一个整数。
假设Alice选择了整数a，Bob选择了整数b。
Alice使得a做如下变换:
a -> 2 * a * (a+1)^2
Bob使得b做如下变换:
b -> b^2
如果变换后的数字相等，则两个人可以化敌为友。
如果不相等，这两个人怕是石乐志。
现在，你想把Bob部分可能的整数b（存在a变换后的数字等于b变换后的数字）从小到大排列后，知道第一个大于等于n的数字是多少。
输入描述:
第一行输入一个整数T，表示数据组数。
每组数据输入一个整数n。
1 <= T <= 100000
0 <= n <= 10^19
保证结果存在
输出描述:
输出一个整数。示例1
输入
3 2 6 100
输出
6 6 114
题解
二分查找。
要使得$ b^2 = 2 * a * (a+1)^2$，即$b= \sqrt{2 * a * (a+1)^2}$。
因为$b$是整数，所以`$\sqrt{2 * a * (a+1)^2}$`也是整数，因此$\sqrt{2 * a}$为整数。
设$p$为整数，则$a$可以表示为$a = 2*p*p$，则$b = 2*p*(2*p*p+1)$，因此二分$p$就可以得到答案了。
最后注意一下溢出的问题。
#include
using namespace std;int T;int main() {scanf("%d", &T);while(T --) {unsigned long long n;scanf("%llu", &n);if(n == 0) {printf("0\n");continue;}unsigned long long L = 0;unsigned long long R = 3e6;unsigned long long ans;while(L <= R) {unsigned long long mid = (L + R) / 2;unsigned long long p = mid * mid * mid * 4LL + mid * 2LL;if(p >= n) {ans = p;R = mid - 1;} else {L = mid + 1;}}printf("%llu\n", ans);}return 0;
}
转载于:https://www.cnblogs.com/zufezzt/p/8080613.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！