给你两个数\(a , b\)，每次可以选择：
- 将第一个数减去\(x\)
- 将第二个数减去\(x\)
- 将第两个数均减去\(x\)
现在求是否必胜，和若必胜，第一步的策略
首先，我们可以发现，这个游戏中，a和b是完全等价的，即状态\((a,b)\)和状态\((b,a)\)没有什么不同，为了方便起见，接下来将只讨论\(a\le b\)的情况
我们可以手算出最开始的几组必败态，它们是\((1,2),(3,3),(4,6),(5,8),(7,11),(9,14)\ldots\)
经过一番维基之后，知道了对于\(a,b\)均大于3的状态\((a-1,b-1)\)，就是Wythoff游戏
对于所有的必败态，它的有\(a_k = \lfloor k \phi \rfloor = \lfloor b_k \phi \rfloor -b_k , b_k = \lfloor k \phi^2 \rfloor = \lceil a_k \phi \rceil = a_k + k\)
其中，\(\phi\)为黄金分割数
于是，通过二分的方法，找到对应的\(k\)，可以知道一个状态是否为必败态
接着，对于必胜态，我们可以二分必败态，找到可以转移过去的必败态，这里也可以通过二分来实现
至于为什么是二分而不是直接求得，这里是考虑到了精度问题
因为输入高达\(10^{12}\)，所以C++中double和long double都存在精度不够的问题，需要使用Java的BigDecimal类来保证精度
最后说一下，这次比赛居然没有英文题解，全靠机译俄文才得以弄清楚
AC-Code
import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;
import java.lang.*;
public class Main {
static BigDecimal sqrt5p1 = new BigDecimal("3.23606797749978969640917366873127623544061835961152572427089");
static BigDecimal r2 = new BigDecimal("2.0");
static BigDecimal phi = sqrt5p1.divide(r2);
static Scanner cin = new Scanner(new BufferedInputStream(System.in));
public static long get_a(long tk) {
return phi.multiply(new BigDecimal(tk)).longValue();
}
public static long get_b(long tk) {
return phi.multiply(new BigDecimal(tk)).longValue() + tk;
}
public static void work() {
boolean flg = false;
long a , b , swp;
a = cin.nextLong();
b = cin.nextLong();
if (b < a) {
swp = b;
b = a;
a = swp;
flg = true;
}
if (a <= 3) {
if (a == 3) {
if (b == 3) {
System.out.printf("2\n");
} else {
if (flg) {
System.out.printf("1 %d 0\n" , b - 3);
} else {
System.out.printf("1 0 %d\n" , b - 3);
}
}
}
if (a == 2) {
if (flg) {
System.out.printf("1 %d 0\n" , b - 1);
} else {
System.out.printf("1 0 %d\n" , b - 1);
}
}
return;
}
if (a == b) {
System.out.printf("1 %d %d\n" , a - 3 , a - 3);
return;
}
if (b == a + 1) {
System.out.printf("1 %d %d\n" , a - 1 , a - 1);
return;
}
a--;
b--;
long k0 = 0;
for (long i = 1l << 40 ; i > 0 ; i >>= 1) {
long rb = get_b(k0 + i);
if (rb <= a) {
k0 += i;
}
}
if (get_b(k0) == a) {
if (get_a(k0) == b) {
System.out.printf("2\n");
return;
}
long ansa = 0;
long ansb = b - get_a(k0);
if (flg) {
swp = ansa;
ansa = ansb;
ansb = swp;
}
System.out.printf("1 %d %d\n" , ansa , ansb);
return;
}
//--
k0 = 0;
for (long i = 1l << 40 ; i > 0 ; i >>= 1) {
long ra = get_a(k0 + i);
if (ra <= a) {
k0 += i;
}
}
if (get_a(k0) == a) {
if (get_b(k0) == b) {
System.out.printf("2\n");
return;
}
if (get_b(k0) < b) {
long ansa = 0;
long ansb = b - get_b(k0);
if (flg) {
swp = ansa;
ansa = ansb;
ansb = swp;
}
System.out.printf("1 %d %d\n" , ansa , ansb);
return;
}
}
k0 = a;
for (long i = 1l << 40 ; i > 0 ; i>>= 1) {
if (k0 - i <= 0)
continue;
long ra = get_a(k0 - i);
long rb = get_b(k0 - i);
long delta = a - ra;
if (b - delta <= rb)
k0 -= i;
}
/*
if (get_a(k0) == a && get_b(k0) == b) {
System.out.printf("2\n");
return;
}*/
long ansa = a - get_a(k0);
System.out.printf("1 %d %d\n" , ansa , ansa);
}
public static void main(String[] args) {
//for (int i = 0 ; i < 10 ; i++)
// System.out.printf("(%d %d)\n" , get_a(i) , get_b(i));
phi.setScale(60 , BigDecimal.ROUND_FLOOR);
int t;
t = cin.nextInt();
for (int i = 0 ; i < t ; i++) {
work();
}
}
}