重複單位可整除性（使用C++）

在本文中，我們將討論找出可被 N 整除的重複單元的數量。重複單元只是 1 的重複數量，令 R(k) 為重複單元，其中 k 為 1 的長度。例如 R(4) = 1111。因此我們需要找到R(k) 可被N 整除的k 的最小數量，例如-

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 整除。

範例

#include <bits/stdc++.h>
using namespace std;

int main() {
   int N = 31;
   int k = 1;
   // checking if N is coprime with 10.
   if (N % 2 == 0 || N % 5 == 0){
      k = 0;
   } else {
      int r = 1;
      int power = 1;
      // check until the remainder is divisible by N.
      while (r % N != 0) {
         k++;
         power = power * 10 % N;
         r = (r + power) % N;
      }
   }
   cout << "Value for k : "<< k;
   return 0;
}

輸出

Value for k : 15

結論

在本文中，我們討論尋找R(k) 的k 值，其中R( k) 是可被給定N 整除的重複單元。我們討論了一種樂觀的方法來找到k 的值。我們也討論了解決這個問題的 C 程式碼。您可以使用任何其他語言（例如 Java、C、Python 等）編寫此程式碼。我們希望本文對您有所幫助。

以上是重複單位可整除性（使用C++）的詳細內容。更多資訊請關注PHP中文網其他相關文章！