主題
題目連結：
題目意譯：
給定一個正整數 k，你需要找到最小正整數 n 之長度使得 n 可被 k 整除且 n 只包含數字 1。
回傳 n 的長度。如果不存在這樣子的 n 值，回傳 -1。
注： n 可能無法被容納進一個 64 位元有號整數內。
限制：
1 ≦ k ≦ 10 ^ 5
範例測資：
範例 1：
輸入： k = 1
輸出： 1
解釋： 最小的答案為 n = 1，其長度為 1。
範例 2：
輸入： k = 2
輸出： -1
解釋： 不存在正整數 n 可以被 2 整除。
範例 3：
輸入： k = 3
輸出： 3
解釋： 最小的答案為 n = 111，其長度為 3。
解題思維：
首先，我們可以看到只要 k 是 2 的倍數或是 5 的倍數就不可能存在題目所敘述的 n 值。因為我們能生成的數字是以 1 結尾的數字，而 2 的倍數至少需要是偶數結尾、5 的倍數則最少需要以 0 或是 5 結尾。
而我們可以看到當我們對以下數字：
1
11
111
1111
……
求餘數的時候等同於前一個數字的餘數乘以 10 再加 1。例如說已知 1111 除以 17 的餘數是 6，則 11111 除以 17 的餘數會是
6 × 10 + 1
除以 17 的餘數。也就是 10。
而餘數可能的值只有 0 ～ k - 1 這 k 個數值而已。因此如果我們做了上述的步驟 k + 1 次（也就是我們最後一項是在算 k + 1 個 1 除以 k 的餘數）的話，則根據鴿籠原理（Pigeonhole Principle）可知至少會有一個餘數值重複了一次。
因此如果我們上述的過程做了 k 次都沒有遇到餘數值為 0 的結果，則代表我們再繼續做下去也不可能遇到。因此此時就可以回傳 -1；反之，過程中有遇到的話就可以回傳這是第幾步，該步數即為所求。
但是實際上本題有更強烈的性質——即除了 2 或 5 的倍數以外的正整數皆存在這樣子的 n 值。而這個結論可以從數論中的歐拉定理（Euler's Theorem）推得：
已知
a ^ φ(k) ≡ 1 (模 k)
其中 a 、 k 為正整數（這邊的 k 可以對應到題目的 k），且 a 和 k 互質（即最大公因數（Greatest Common Divisor，GCD）等於 1），而 φ(k) 為歐拉總計函數（Euler's Totient Function），即 1（含）～ k（含）的正整數有多少與 k 互質。並且，上式當中的特殊等號「≡」代表「同餘」，也就是等號左右除以 k 之後的餘數（模 k）是相同的。
此時我們可以看到當 a 代入 10，並把等號右側的 1 丟到左側得到
10 ^ φ(k) - 1 ≡ 0 (模 k)
可以看到等號左邊是一個只由 9 組成的數字，且根據我們的 k 值之條件（不為 2 或 5 的倍數），等號會成立。因此，我們把等號左右兩邊同除以 9，得到
(10 ^ φ(k) - 1) ÷ 9 ≡ 0 (模 k)
此時等號左邊的數字便成為了只由 1 組成的數字。但是此時由於餘數除法只適用於模反元素（Modular Inverse，如這題）在的時候，也就是說此時上式只適用於 k 與 9 互質的時候。
因此我們少了所有 3 的倍數，需要額外證明才行。首先，假設我們現在有一數字 X，其為 3 的倍數。因此我們可以將 X 寫為 3 ^ d × m，其中 d ≧ 0 且 m 為一個不為 3 的倍數之正整數。
因此這邊的 m 可以根據上面歐拉定理推出自己的 n 值；而我們可以使用類似於這題的論述來證明所有 3 的某次方（即上式的 3 ^ d）也會有對應的 n 值。已知 m 與 3 ^ d 互質，因此我們可以藉由中國剩餘定理（Chinese Remainder Theorem）來得到整個 X 的 n 值。
以上，我們便證明了對於所有不是 2 或是 5 的倍數之正整數皆「存在」對應的 n 值。
結合我們一開始的結論——「最多做 k 次便可以判斷有沒有。」此時我們先排除掉 2 和 5 的倍數後，剩下可能的數字 k 必定會在 k 步以內找到餘數為 0 的 n 值。
因此不需額外判斷會不會碰到餘數 0（因為一定會有）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
