51nod

思路：很容易证明合法的总分是n^2。那么n就是游戏的回合数。那么总的回合数最多就是sqrt(2e12)。然后求A最少胜几盘相当于B最多胜几盘。假设B总是在低回合中胜出，那么同样的分数，他能胜的盘数更多。于是假设B从第一局就开始胜，这样贪心去取分数，就能求出B最多能胜几盘。值得注意的是，B胜的回合数跟B的分数应该是同奇偶的。最后特判一下2分的情况，在这个游戏中，这个分数不可能出现。

复杂度分析：我先预处理出所有的B的情况，1e6，然后再二分查找，总的复杂度为 O(T*sqrt(x+y)log(sqrt(x+y)))。最后发现太傻逼了，直接sqrt(b)不就好了么。。。。对的，最后复杂度为O(T*log(sqrt(x+y)))。【O(log(sqrt(x+y))) 为求开根号的复杂度】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 //const ll maxn = 1e12 + 100;
 6 // std::vector<ll> sq;
 7 // void init() {
 8 //     for(int i=0; i<1414215; i++) {
 9 //         sq.push_back(1LL*i*i);
10 //     }
11 // }
12 int main() {
13     //init();
14     int T;
15     scanf("%d", &T);
16     while(T--) {
17         ll a, b;
18         scanf("%lld%lld", &a, &b);
19         ll s = sqrt(a+b+0.5);
20         if(s*s != a+b) printf("-1
");
21         else if(a==2 || b==2) printf("-1
");
22         else {
23             // int l = lower_bound(sq.begin(), sq.end(), b) - sq.begin();
24             // if(sq[l] != b) {
25             //     l --;
26             //     l -= (b+l)&1;
27             // }
28             int l = sqrt(b+0.5);
29             l -= (b+l)&1;
30             printf("%lld
", s - l);
31         }
32     }
33     return 0;
34 }