ALL：6
AC：4
补题：0
Rank：729
–
题意：
给定非负整数 a , b a,b a,b，你可以进行下面的操作任意次：
求出经过若干次操作后
gcd
(
a
,
b
)
\gcd(a,b)
gcd(a,b) 的最大值，并求出至少需要多少次操作以获得这个最大值。特别的，如果
gcd
(
a
,
b
)
\gcd(a,b)
gcd(a,b) 可以变成无限大，输出 0 0。
T
T
T 组数据。
注意
x
≥
0
x\geq 0
x≥0 时
gcd
(
x
,
0
)
=
x
\gcd(x,0)=x
gcd(x,0)=x。
数据范围： 1 ≤ T ≤ 5 × 1 0 3 1\leq T\leq5\times10^3 1≤T≤5×103， 0 ≤ a , b ≤ 1 0 18 0\leq a,b\leq10^{18} 0≤a,b≤1018。
思路：最大值为 ∣ a − b ∣ |a-b| ∣a−b∣ ，即当 a = 2 ⋅ b , a > b a=2\cdot b,a>b a=2⋅b,a>b 时取得。赛时直接猜的结论，要证明的话使用 gcd ( a , b ) = gcd ( b , a − b ) \gcd(a,b)=\gcd(b,a-b) gcd(a,b)=gcd(b,a−b) 证明即可。
AC代码：https://codeforces.com/contest/1543/submission/178761502
题意：题意好麻烦。略。详见 洛谷 。
思路：刚开始没敢写爆搜，开 D 开不出来之后写了爆搜居然能过（。 d f s dfs dfs 求一下期望即可，搜索大概 1 0 5 10^5 105 级别的。
AC代码：https://codeforces.com/contest/1543/submission/178766680
题意：
这是本题的简单版本，简单版本和困难版本的区别在于
k
k
k 的数据范围，在简单版本中
k
=
2
k=2
k=2。
本题是交互题。
对于十进制数
a
,
b
a,b
a,b，我们定义
a
⊕
k
b
a\oplus_kb
a⊕kb 的值如下：
交互器会告诉你整数
n
,
k
n,k
n,k，同时交互器有一个你不知道的整数
x
x
x，你知道
x
∈
[
0
,
n
−
1
]
x\in[0,n-1]
x∈[0,n−1]，你需要在
n
n
n 次猜测中猜出
x
x
x 的值。每次猜测你需要输出整数
y
y
y，如果
x
=
y
x=y
x=y 那么本组数据交互正确结束，交互器会输入
1
1
1，你应该处理下一组数据（如果有的话），如果
x
≠
y
x\not=y
x=y，交互器会输入
0
0
0 同时改变
x
x
x 的值，
x
x
x 的值会变为整数
z
z
z，其中
x
⊕
k
z
=
y
x\oplus_kz=y
x⊕kz=y。
T
T
T 组数据。
1
≤
T
≤
1
0
4
;
1
≤
n
,
∑
n
≤
2
×
1
0
5
;
k
=
2
;
1\leq T\leq10^4;1\leq n,\sum n\leq2\times10^5;k=2;
1≤T≤104;1≤n,∑n≤2×105;k=2;
思路：赛时猜的结论，输出 i ⊕ ( i − 1 ) , i ∈ [ 0 , n − 1 ] i\oplus (i-1),i\in[0,n-1] i⊕(i−1),i∈[0,n−1] 即可。因为这样可以把之前询问的影响消除掉。
AC代码：https://codeforces.com/contest/1543/submission/178767646