Strange Homura Game 题解
wxzzzz
·
·
题解
思路
先简化一下式子：
&\begin{cases}
x_1=am+b\\
x_2=cm+d
\end{cases}\\
&\begin{cases}
x_1\equiv b\pmod m\\
x_2\equiv d\pmod m
\end{cases}\\
&\begin{cases}
x_1-b\equiv 0\pmod m\\
x_2-d\equiv 0\pmod m
\end{cases}\\
&\begin{cases}
m\mid(x_1-b)\\
m\mid(x_2-d)
\end{cases}
\end{aligned}
相当于 m\mid\gcd(x_1-b,x_2-d)。
到这里还是无法直接确定 m，因为 \gcd 可能有多个因数。
显然 x_1,x_2 必须 >10^{17} 否则可能 \le m 浪费询问机会。
构造 x_1=10^{17}+3（大质数），令 c_1=x_1\bmod m。
构造 x_2=2(x_1-c_1)-1，令 c_2=x_2\bmod m。
证明：数学直觉。
### 代码
```cpp
#include <bits/stdc++.h>
#define ll long long
#define N 10
using namespace std;
ll P1 = 100000000000000003, P2;
ll qpow(ll x, ll k, ll MOD) {
ll ret = 1, base = x;
while (k) {
if (k & 1)
ret = (ret * base) % MOD;
base = (base * base) % MOD;
k >>= 1;
}
return ret;
}
ll gcd(ll x, ll y) {
while (x ^= y ^= x ^= y %= x);
return y;
}
ll T, c1, c2;
int main() {
scanf("%lld", &T);
while (T--) {
printf("? %lld\n", P1);
fflush(stdout);
scanf("%lld", &c1);
P2 = (P1 - c1) * 2 - 1;
printf("? %lld\n", P2);
fflush(stdout);
scanf("%lld", &c2);
printf("! %lld\n", gcd(P1 - c1, P2 - c2));
fflush(stdout);
}
return 0;
}
```