给定两个整数\(a,b\),你可以执行以下操作任意次：每次操作选择一个正整数\(x\)，使得\(a:=a-x,b:=b-2x\)或者\(a:=a-2x,b:=b-x\)，问你是否能通过操作使得\(a,b\)都为同时为\(0\)

假设\(a\(a+b=3x\)，显然我们可以得到如果我们能通过操作使得\(a,b\)同时为\(0\)，我们可以得到$3\ |\ (a+b) $ 但是一定存在限制条件，比如说\(a=1,b=8\)时，就无法同时变为\(0\)，我们不妨令\(x=1\)，我们发现\(a-=1,b-=2\)会使得\(b\)和a之间的差距缩小\(1\)，如果在\(a\)变为\(0\)之前\(b\)还没有追上\(a\)，那一定无法同时为\(0\)，当时的情况一定是\(a=0,b>0\)，如果在\(a\)变为\(0\)之前\(b\)已经追上了\(a\)，我们经过模拟之后发现，\(a\)和\(b\)之间只要交替\(-1\)，\(-2\)就能实现同时为\(0\)，所以我们只要判断在\(a\)变为\(0\)之前\(b\)有没有追上\(a\)即可 #include #define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0) #define debug(x) cerr d; p[i] = {l, r, d}; } int l = 1, r = m; while (l > 1; if (check(mid)) l = mid + 1; else r = mid - 1; } cout T; while (T--) { solve(); } return 0; } E - Tournament

一场拳击比赛中有\(n\)个人，\(n\)是\(2\)的幂次，其中有一个人是你的朋友，你可以任意安排两两配对进行比赛，这\(n\)个人按照能力大小排列，且能力为\(i\)的人能被贿赂的代价为\(a_i\)，如果能力强的人对局能力弱的人，那么能力弱的人就会被淘汰，但是我们可以通过贿赂来使得能力强的故意输掉比赛，如果\(a_i=-1\)，则代表这个人是你的朋友，现在你需要帮助你的朋友取得冠军 ，请你求出最少需要花费多少代价使得朋友获得冠军

首先我们通过模拟可以知道，假设现在不贿赂任何人，并且任意安排的对局，我们可以发现：

冠军永远只有\(1\)个，那就是编号为\(n\)的选手

能够进入\(2\)强的人只会出现在\([\frac{n}{2},n]\)中

能够进入\(4\)强的人只会出现在\([\frac{n}{4},n]\)

......

​ 我们知道编号大的人能够存活下来的概率越大，所以我们优先贿赂编号大的人

​ 所以我们得到现在我们的朋友通过安排特定的对局最多能够到达的排名，如果朋友现在处于\([\frac{n}{2},n]\)中，说明我们可以通过安排对局使得朋友成为\(2\)强，最后我们只需要贿赂编号为\(n\)的人（也就是原本的冠军）即可

​ 如果朋友现在处于\([\frac{n}{4},n]\)中，说明我们可以通过安排对局使得朋友成为\(4\)强，但是我需要多贿赂一个人，也就是说我需要贿赂一名本身能够成为\(2\)强的选手让他故意故意输给朋友即可，那么我们只需要在\([\frac{n}{2},n]\)中找一个贿赂代价最小的人贿赂即可，因为这个人的实力本来就可以通过安排对局没有任何花费的使他进入\(2\)强

​ 依次类推，所以我们只需要维护一个区间中的最小值即可，我们考虑利用优先队列实现