- 通過研究，偶數(shù)乘以任何數(shù)都是偶數(shù)結(jié)尾，所以不會以1結(jié)尾。同理5乘以任何數(shù)要么是0要么是5. 不會以1結(jié)尾。
寫出如下代碼
if (K % 2 == 0 || K % 5 == 0) return -1;
- 余數(shù)的性質(zhì)
枚舉N 從1,11,111，。。。為了防止整數(shù)溢出，運(yùn)用余數(shù)定理。
n的變化公式為
初始狀態(tài)n=0,
遞推公式 n = 10 *n + 1;
證明
(10 * n + 1) % K = (10 * (n % K) + 1) % K
=> (10 % K) * (n % K) + (1% K) = (10 % K) * (n % K % K) + (1 % K)
因?yàn)?N % K % K = N % K
所以上述等式成立
寫出如下代碼
int n = 0;
int step = 1;
while (true) {
n = n *10 + 1;
int tmp = n % K;
if (tmp == 0) return step;
step++;
n = tmp;
}
上述有個投機(jī)的做法來防止無限循環(huán)，就是用個SET，之前出現(xiàn)的過余數(shù)再出現(xiàn)，就可以BREAK， RETURN -1。因?yàn)檫M(jìn)入了輪回，沒必要再做下去了。
- 論證必定有解（反證法）
a. K個1（111111...111），下面簡寫為K（1）。MOD K，假設(shè)沒有解。那么余數(shù)的范圍應(yīng)該【1，K - 1】一共K-1個可能。
b. 從1 開始 到K個1， 每一次取余，一共有K 個 余的結(jié)果 。 那么必定有2個結(jié)果是相同的。
c. 假設(shè)第I次取余 和 第J次取余的結(jié)果相同。（i > j）
d. i - j = (i - j) 個 1， j 個0 -> 1111..11 * 100..000
e. 2個數(shù)MOD K的余數(shù)相同，他們的差 必定能被K整除。
f. 11..1100..00 % K = 0 ， （11..11）% K * (100..00)%K = 0, 因?yàn)?if (K % 2 == 0 || K % 5 == 0) return -1; 所以 11..11 % K =0. 與假設(shè)矛盾
