在本文中，我們將討論找出可被 N 整除的重複單元的數量。重複單元只是 1 的重複數量，令 R(k) 為重複單元，其中 k 為 1 的長度。例如 R(4) = 1111。因此我們需要找到R(k) 可被N 整除的k 的最小數量，例如-
1 2 3 4 5 6 | Input : N = 13
Output : k = 6
Explanation : R(6) i.e 111111 is divisible by 13.
Input : N = 31
Output : k = 15
|
登入後複製
尋找解決方案的方法
您可以透過檢查從1 開始的k 的每個值來解決此問題，其中R(k) 能否被N 整除。但使用此解，我們將無法確定 N 是否可被 R(k) 的任何值整除。這將使程式變得過於複雜，甚至可能無法運行。
解決程式的有效方法是，
- 檢查 N 是否與 10 互質。
- 如果不是，則對於任何 k 值，R(k) 都不能被 N 整除。
- 如果是，則對於每個重複單元R(1)、R(2)、R(3)...等等，計算R(i)與N相除的餘數，因此餘數有n個。
- 找出R(i) 和R(j) 的相同餘數，其中R(i) 和R(j) 是兩個重複單元，以便R(i) - R(j) 可被N 整除.
- aR(i) 和R(j) 的差將重複單位乘以10 的某個冪，但10 和N 互質，因此R(k) 將被N 整除。
範例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <bits/stdc++.h>
using namespace std;
int main() {
int N = 31;
int k = 1;
if (N % 2 == 0 || N % 5 == 0){
k = 0;
} else {
int r = 1;
int power = 1;
while (r % N != 0) {
k++;
power = power * 10 % N;
r = (r + power) % N;
}
}
cout << "Value for k : "<< k;
return 0;
}
|
登入後複製
輸出
結論
在本文中，我們討論尋找R(k) 的k 值，其中R( k) 是可被給定N 整除的重複單元。我們討論了一種樂觀的方法來找到k 的值。我們也討論了解決這個問題的 C 程式碼。您可以使用任何其他語言（例如 Java、C、Python 等）編寫此程式碼。我們希望本文對您有所幫助。
以上是重複單位可整除性（使用C++）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
