题目描述
You are given three integers $ a $ , $ b $ , and $ d $ . Your task is to find any integer $ x $ which satisfies all of the following conditions, or determine that no such integers exist:
- $ 0 \le x \lt 2^{60} $ ;
- $ a|x $ is divisible by $ d $ ;
- $ b|x $ is divisible by $ d $ .
输入格式
Each test contains multiple test cases. The first line of input contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.
Each test case consists of one line, containing three integers $ a $ , $ b $ , and $ d $ ( $ 1 \le a,b,d \lt 2^{30} $ ).
输出格式
For each test case print one integer. If there exists an integer $ x $ which satisfies all of the conditions from the statement, print $ x $ . Otherwise, print $ -1 $ .
If there are multiple solutions, you may print any of them.
样例 #1
样例输入 #1
8
12 39 5
6 8 14
100 200 200
3 4 6
2 2 2
18 27 3
420 666 69
987654321 123456789 999999999
样例输出 #1
18
14
-1
-1
0
11
25599
184470016815529983
提示
In the first test case, $ x=18 $ is one of the possible solutions, since $ 39|18=55 $ and $ 12|18=30 $ , both of which are multiples of $ d=5 $ .
In the second test case, $ x=14 $ is one of the possible solutions, since $ 8|14=6|14=14 $ , which is a multiple of $ d=14 $ .
In the third and fourth test cases, we can show that there are no solutions.
注意，后面的 \(|\) 都是代表按位或，而不是整除。
要让 \(a|x\) 是 \(d\) 的倍数，让 \(b|x\) 是 \(b\) 的倍数。要同时让两个数满足不好写，所以尝试让 \(a|x=b|x=x\)，并让 \(x\) 位 \(d\) 的倍数。
为什么敢于放到这一步呢？其实发现 \(x\) 的取值范围很大，所以极有可能达到这个条件。要满足上面这个条件，不妨让 \(x\) 的后 30 位就是 \(a|b\) 就行了
换句话说，\(x\equiv a|b\pmod{2^{30}}\)
如果把 \(x\) 表示为 \(dk\)，那么就是 \(dk\equiv a|b\pmod{2^{30}}\)，拿个exgcd 就好了。exgcd 的解是肯定符合要求的，同时如果 exgcd 无解，肯定原来也无解。
但是有一个更简单的方法。
原方程有解的条件是 \(\gcd(d,2^{30})\) 能整除 \(a|b\)，而 \(\gcd(d,2^{30})\) 就是 \(\mathrm{lowbit(d)}\)，那么可以通过不断除以 2 来判断。最后如果有解的时候，\(d\) 的最后一位已经被除成 1 了。现在假设答案 \(ans\) 满足了前 \(j-1\) 位与 \(a|b\) 相等，但是第 \(j\) 位与 \(a|b\) 不等，那么可以让 \(ans\) 加上 \(d\times 2^j\)。那么此时答案的这一位会发生变化，然后一直弄到 \(a|b\) 已经全部被模仿出来。
由于 \(a|b<2^{30}\)，解合法。
#include<bits/stdc++.h>
using namespace std;
int a,b,d,t,p,cnt;
long long ret;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&a,&b,&d);
a|=b,p=1<<30,ret=cnt=0;
while(!(d&1)&&!(a&1))
a>>=1,d>>=1,p>>=1,++cnt;
if(!(d&1))
{
printf("-1\n");
continue;
}
// printf("%d %d %d\n",a,d,p);
for(int i=0;(1LL<<i)<=p&&(1LL<<i)<=a;i++)
{
if((ret>>i&1)!=(a>>i&1))
ret+=(1LL*d)<<i;
// printf("%d\n",ret);
}
printf("%lld\n",ret*(1LL<<cnt));
}
}