自动搬运

查看原文

来自洛谷，原作者为

	asd890123 蒟蒻

搬运于2025-08-24 23:04:38，当前版本为作者最后更新于2024-10-02 21:38:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

将题目进一步形式化：

输出 $p_1$和 $p_2$ ，评测机会给出对应的 $r_1$ 和 $r_2$

$m \bmod p_1 = r_1$

$m \bmod p_2 = r_2$

我们令

$p1 = 4 \times 10^8$

$p2 = p1 - 1$

相邻两数必然互素， $p_1 , p_2$ 互素。

构造一组 $k_1,k_2$ 使得：

$k_1p_2 \bmod p_1 = r_1$

$k_2p_1 \bmod p_2 = r_2$

得：$k_1 = p_1 - r_1,k_2 = r_2$ 即可满足

所以 $m = [(p_1 - r_1)p_2 + p_1r_2] \bmod p_1p_2$

代码：

#include <iostream>

typedef long long LL;

const LL Max = 4e8;
const LL mod = (LL)1e17 + 1;

int main(){

    std::cin.tie(0)->sync_with_stdio(0);

    int T;

    for (std::cin >> T;T--;){

        LL res1,res2;

        std::cout << "? " << Max << std::endl;
        std::cin >> res1;
        std::cout << "? " << Max - 1 << std::endl;
        std::cin >> res2;
        std::cout << "! " << (Max * res2 + (Max - 1) * Max - (Max - 1) * res1) % (Max * (Max - 1)) << '\n';

    }

    return 0;
}