整除光棍（附简要证明）

本文主要是介绍整除光棍（附简要证明），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

整除光棍

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

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

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

输入样例：

31

输出样例：

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