整除光棍（附简要证明）

科技前沿 • 2025-02-14 17:19 • 阅读 38

大家好，我是讯享网，很高兴认识大家。

整除光棍

这里所谓的“光棍”，并不是指单身汪啦~ 说的是全部由1组成的数字，比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如，就可以被13整除。现在，你的程序要读入一个整数x，这个整数一定是奇数并且不以5结尾。然后，经过计算,

输出两个数字：第一个数字s，表示x乘以s是一个光棍，第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。

提示：一个显然的办法是逐渐增加光棍的位数，直到可以整除x为止。但难点在于，s可能是个非常大的数 —— 比如，程序输入31，那么就输出81和15，因为31乘以81的结果是1111，一共15个1。

输入样例：

31

输出样例：

81 15

解：

[分析]:题目已经提示s可能是个非常大的数，s估计只能用字符串来表示了。
这个时候就要想到求余(%).
1.引入第一个推论
条件：d = ab+c
d%p = ((ab)+c)%p =( b(a%p)+c)%p
证明：d%p = ((a*b)+c)%p =( b(a%p)+c)%p
（在此谢谢大佬给的思路！）
任意一个数c都能表示成 d = ab +c,(任意b)的格式（欧几里得除法)
因为：d = ab + c
所以：d % p = (ab + c) % p
设t = b % p,所以 b = kp + t
要证明的式子变成： d%p = ((ab)+c)%p =( a*t+c)%p

((ab)+c)%p = (a * (kp + t) + c)%p = (at + c)%p

证毕

设x₁=111%37

1111%37 = (111*10+1)%37 = ((111%37)*10+1)%37
1111%37 = (x₁ * 10+1)%37

讯享网

设x₂ = 1111%37

11111%37 = (x₂ * 10 + 1)%37
递推规则出来了

2.引入第二个结论

111 与 31
111 % 31 = 18
1111 / 31 = 3
s = ‘3’ (s为字符串)
num = 18
1111 与 31
1111 % 31 = 26 1111 / 31 = 35
（111 % 31 = 18）
18 * 10 + 1 = 181
(此时的181%31的结果等价于1111%31的结果)
181 % 31 = 26
181 / 31 = 5(在递推过程中这个数是小于10的)
证明：在递推过程中这个数是小于10的
用g来表示光棍数，x = 31
即证:
$\frac{10 * (g\%x) + 1}{x} < 10$
$\frac{10 * (g\%x) + 1}{x} < \frac{10 * (x - 1) + 1}{x} = \frac{10 * x -9}{x} < 10$

证毕

s +=‘5’（即’3’+‘5’ s==“35”）
一直递推下去

 Created by tiffa on 2020/3/29. #include<iostream> #include <cstring> using namespace std; int main() { 
    int x; cin>>x; string s; int len = 1; int num = 1; while(num < x){ 
    num = num * 10 + 1; len ++; } while (num % x != 0){ 
    s += (num / x) + '0'; num = num % x; num = 10*num + 1; if(num%x == 0) break; len++; } s += (num / x) + '0'; len++; cout<<s<<" "<<len; return 0; }

讯享网

输出结果

在这里插入图片描述
参考资料：
参考博客

整除光棍（附简要证明）

整除光棍

输入样例：

输出样例：

解：

输出结果

相关推荐