首頁  >  文章  >  後端開發  >  重複單位可整除性(使用C++)

重複單位可整除性(使用C++)

王林
王林轉載
2023-08-26 22:37:121418瀏覽

重複單位可整除性(使用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中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除