hdu6869 Slime and Stones // 威佐夫博弈·改

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6869

威佐夫博弈原本是每次操作任取某堆的任意个石头₁，或是从两堆中分别取出相同数量的石头₂

方程为：

　　　　　　1 / t + 1 / t + 1 = 1;

当操作2修改为取出石头数量之差不超过k，即本题含义时，方程可为：

　　　　　　1 / t + 1 / 1 + k + t = 1;

　判定条件为： a_n = n * t;

　　　　　　     b_n = a_n + (k + 1) * n;

　若属于数列元素——lose　　其余点——win　　[本题中讨论先手情况]

本文借鉴CSDN某萌萌哒大佬：https://blog.csdn.net/qq_43814654/article/details/108086427

*转载请附链接 谢谢

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>

#define ll long long

using namespace std;

bool check(ll a, ll b, ll k)// 1/x + 1/1+k+x = 1 | x = ? 
{
    long double K = k; 
    long double t = (1.0 - K + sqrt(K * K + 2 * K + 5.0)) / 2.0;
    //直接用long double 代入运算 方程解的精度很致命 
        
    ll l = 0, r = 1e9, mid;
    while(l <= r){
        mid = (l + r) >> 1;
        ll tmp = (k + 1 + t) * mid;
        if(b > tmp){
            l = mid + 1;
        }else if(b < tmp){
            r = mid - 1;
        }else{
            if(a + (k + 1) * mid == b){
                return true;
            }
            break;
        }
    }    
    return false;
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        ll a, b, k;
        scanf("%lld%lld%lld",&a,&b,&k);
        if(a > b)    swap(a, b);
        if(check(a, b, k)){//true-lose false-win
            printf("0
");
        }else{
            printf("1
");
        }                
    }
        
    return 0;
}