我在網上找到了這個問題，我真的不知道這個問題在問什么。如果可能的話，我真的很感激在首先理解這個問題和解決方案方面的一些幫助。謝謝！
要查看一個數是否能被 3 整除，您需要將其十進制表示法的位數相加，并檢查和是否可被 3 整除。要查看一個數是否可??被 11 整除，您需要將其十進制表示法拆分為一對數字（從右端開始），將相應的數字相加并檢查總和是否可以被 11 整除。
對于任何素數 p（除了 2 和 5），都存在一個整數 r，因此存在類似的可除性測驗：要檢查一個數字是否可被 p 整除，您需要將其十進制表示法拆分為 r 個數字元組（從右端），將這些 r 元組相加并檢查它們的總和是否可以被 p 整除。
給定一個素數 int p，找到這種可分性測驗有效的最小 r 并將其輸出。
輸入由單個整數 p 組成 - 介于 3 和 999983 之間的素數，包括 3 和 999983，不等于 5。
例子
輸入
3
輸出
1
輸入
11
輸出
2
uj5u.com熱心網友回復：
我不知道他們如何期望一個沒有背景的隨機程式員從中找出答案。
但這里是對模算術的簡要介紹，應該可以做到這一點。
在編程中，n % k是模運算子。它指的是取余數n / k。它滿足以下兩個重要性質：
(n m) % k = ((n % k) (m % k)) % k
(n * m) % k = ((n % k) * (m % k)) % k
正因為如此，對于任何k我們都可以認為具有相同余數的所有數字在某種程度上是相同的。結果是所謂的“整數模k”。它滿足你習慣的大部分代數規則。你有結合性質，交換性質，分配律，加0，乘1。
但是，如果k是一個合數10，那么不幸的是，2 * 5 = 10這意味著模10, 2 * 5 = 0。這對分工來說是個問題。
但是，如果k = p是一個素數，那么事情就會變得容易得多。如果(a*m) % p = (b*m) % p那么((a-b) * m) % p = 0可以(a-b) * m被 整除p。因此要么 要么(a-b)可m被 整除p。
對于任何非零余數m，讓我們看一下序列m % p, m^2 % p, m^3 % p, ...。這個序列是無限長的，只能p取值。所以我們必須有一個重復 wherea < b和m^a % p = m^b %p。所以(1 * m^a) % p = (m^(b-a) * m^a) % p。由于m不除p，也不除，m^a因此m^(b-a) % p = 1。此外m^(b-a-1) % p行為就像m^(-1) = 1/m. （如果你做足夠的數學，你會發現乘法下的非零余數是一個有限群，所有余數形成一個域。但我們忽略它。）
（我要放棄% p無處不在。假設它在任何計算中都存在。）
現在讓我們a成為最小的正數，使得m^a = 1。然后1, m, m^2, ..., m^(a-1)形成一個長度的回圈a。對于任何一個我們n都1, ..., p-1可以形成一個回圈（可能相同，可能不同）n, n*m, n*m^2, ..., n*m^(a-1)。可以看出，這些回圈劃分1, 2, ..., p-1，其中每個數字都在一個回圈中，并且每個回圈都有長度a。因此，a劃分p-1。作為旁注，由于a除p-1，我們很容易得到有余數
對于“數字的 r 元組” b_i的任何選擇{ 0, ..., 10^r - 1 }（只有有限多個b_i非零）。
考慮b_1 = 1和所有其他b_i = 0，很容易看出有必要
更容易看出這也足夠了（10^ri左側的所有內容都簡單地轉換為1不做任何事情的因素）。
現在，如果p既不是2也不是5，那么10就不能被 整除p，所以費馬小定理保證我們
，即至少r = p - 1存在解。不過，這可能不是最小的，如果手邊沒有量子計算機，計算最小的會很r困難。
盡管一般來說很難，但對于非常小p的 ，您可以簡單地使用線性演算法p（您只需查看序列
10 mod p
100 mod p
1000 mod p
10000 mod p
...
并在找到等于1 mod p) 時立即停止。
寫成代碼，例如，在 Scala 中：
def blockSize(p: Int, n: Int = 10, r: Int = 1): Int =
if n % p == 1 then r else blockSize(p, n * 10 % p, r 1)
println(blockSize(3)) // 1
println(blockSize(11)) // 2
println(blockSize(19)) // 18
或在 Python 中：
def blockSize(p: int, n: int = 10, r: int = 1) -> int:
return r if n % p == 1 else blockSize(p, n * 10 % p, r 1)
print(blockSize(3)) # 1
print(blockSize(11)) # 2
print(blockSize(19)) # 18
一堵數字墻，以防萬一其他人想要檢查替代方法：
11 -> 2
13 -> 6
17 -> 16
19 -> 18
23 -> 22
29 -> 28
31 -> 15
37 -> 3
41 -> 5
43 -> 21
47 -> 46
53 -> 13
59 -> 58
61 -> 60
67 -> 33
71 -> 35
73 -> 8
79 -> 13
83 -> 41
89 -> 44
97 -> 96
101 -> 4
103 -> 34
107 -> 53
109 -> 108
113 -> 112
127 -> 42
131 -> 130
137 -> 8
139 -> 46
149 -> 148
151 -> 75
157 -> 78
163 -> 81
167 -> 166
173 -> 43
179 -> 178
181 -> 180
191 -> 95
193 -> 192
197 -> 98
199 -> 99
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/495355.html
上一篇：及時預測圓到圓的交點