51Nod-1390-游戏得分

1390 游戏得分 题目来源：  TopCoder 基准时间限制：1 秒 空间限制：131072 KB 分值: 40  难度：4级算法题  收藏  关注 A与B两人玩一个游戏，这个游戏有若干个回合（可能0回合）。游戏的回合依次标号为1,2,3，4...。你不需要关心游戏的内容，现在只要知道第i回合胜者会获得2*i-1分，每回合游戏不存在平局。现在已知A和B在游戏结束时各获得了x分与y分的总分。问A在这个游戏中至少获胜了几盘？如果给出的x与y一定不会出现那么输出-1. Input 多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5 每组测试数据有相同的结构构成： 每组数据一行包含两个整数x,y，表示A与B最后的总得分，其中0<=x,y<=1,000,000,000,000。 Output 每组数据一行输出，即A最少获胜了几盘，非法的x与y对输出-1。 Input示例 3 8 17 17 8 0 0 Output示例 2 3 0 孔炤  (题目提供者) 题解： 由每轮得分情况可以看出，其每轮得分比为公差为2的等差数列； 由前n项和公式可以看出，当a+b为完全平方数时才有解 其次，求a的最少回合数就是求b赢的最大回合数 b赢的回合数的特性在于b的得分和赢得回合其奇偶性要一致。 #include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> using namespace std; typedef long long ll; #define maxn 1000005 int main() { ll a,b,T,i,j,ans,t,x; scanf("%lld",&T); while(T--) { ans=0; scanf("%lld%lld",&a,&b); x=sqrt(a+b+0.5); if(x*x!=a+b || a==2 || b==2) { printf("-1\n"); continue; } t=sqrt(b+0.5); t-=(b+t)&1; printf("%lld\n",x-t); } }