【题解】CF2140B Another Divisibility Problem

· · 题解

题意理解

题目先给一个数 x，算出 y。接着把 x 和 y 拼接起来得到一个新数 k，要求满足 (x + y) 能整除 k。

举个例子：如果 x=12，假设 y=34，那拼接后的 k 就是 1234，这时候要检查 12+34=46 能不能整除 1234。

很明显不能，所以 y \neq 34。

思路推导

比如 x=12（2 位）、y=345（3 位），拼接后是 12345，这个结果其实是 12 \times 10^3 + 345。

所以总结出规律：如果 y 有 d 位数字，那么拼接后的数 k = 10^d \times x + y。这一步是整个推导的基础，必须先想明白。

题目核心要求是 (x + y) 能整除拼接后的数 k。

根据之前得出的拼接公式 k = 10^d \times x + y，这个整除关系用同余表示就是：10^d \times x + y \equiv 0 \pmod{x + y}。

这里可以用一个同余的小技巧简化式子：因为 x + y 本身除以 x + y 的余数是 0，即 x + y \equiv 0 \pmod{x + y}，把 x 移到等号右边就能得到 y \equiv -x \pmod{x + y}。

也就是 y 和 -x 除以 x + y 的余数相同。

把 y \equiv -x \pmod{x + y}。

代入之前的同余式 10^d \times x + y \equiv 0 \pmod{x + y}。

把 y 替换成 -x，就能得到 10^d \times x + (-x) \equiv 0 \pmod{x + y}。

再把左边的 x 提取出来整理，最终简化为 (10^d - 1) \times x \equiv 0 \pmod{x + y}。

要让 (10^d - 1) \times x 能被 x + y 整除，最直接的办法就是让 x + y 等于 10^d - 1。

因为 10^d - 1 是 (10^d - 1) \times x 的约数，肯定能整除。

这样一来，y = (10^d - 1) - x，接下来只要确定 d 的值就行。

题目要求 y < 10^9，同时 x < 10^8。我们先假设 d=9。

因为 y = (10^d - 1) - x 且 10^d - 1 = 10^9 - 1 = 999999999。

等量代换 y=999999999 - x。

因为 x < 10^8，所以 y 最小是 9.99999999 \times 10^9- 9.9999999\times 10^8 = 9 \times 10^8，显然满足 y < 10^9，而且 y 的位数正好是 9 位，完全符合条件。

所以结论就是：y = 999999999 - x。

代码实现

AC 记录。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long x;
        cin>>x;
        cout<<999999999 - x<<endl;
    } 
    return 0;
}

本文是以该大佬的文章为基础，进行更详细的补充。