【题解】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

的值就行。

最后，确定 $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 记录。

CPP

#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;
}

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

【题解】CF2140B Another Divisibility Problem

文章操作

题意理解

思路推导

代码实现

相关推荐

评论

【题解】CF2140B Another Divisibility Problem