最小迴圈單位中1的個數

---

在這個問題中，我們只需要列印最小迴圈單位中1的個數。

在趣味數學中，迴圈單位是一個正數，例如11、111或1111，它只包含數字1。迴圈單位的形式為$\mathrm{(10*n-1)/9}$

示例

$\mathrm{(10*10-1)/9}$ 得到 11。

$\mathrm{(10*100-1)/9}$ 得到 111。

$\mathrm{(10*1000-1)/9}$ 得到 1111。

上述問題指出，給定任何一個個位數為3的正整數N，我們需要確定能被給定數字N整除的最小迴圈單位。

例如：

如果給定N=13。

輸出：6

N，即13，可以完美地整除111111，結果為8547。

111111是最小的能被13整除的迴圈單位。因此，最小迴圈單位中1的個數為6，這就是所需的輸出。

演算法

我們知道迴圈單位是1、11、111、1111等等。x之後的下一個迴圈單位可以定義為$\mathrm{(x*10+1)}$。

此演算法基於這樣一個概念：如果整數N的餘數為rem，則迴圈單位的餘數將始終為$\mathrm{(rem*10+1)\%N}$。

確定迴圈單位的數字可能非常繁瑣，因為數字可能非常大，因此我們將透過更新余數直到其變為0，並在每一步更新1的個數來找到答案。使餘數變為0所需的迭代次數就是最小迴圈單位中1的個數。

以下是演算法的逐步描述：

• 步驟1 − 宣告變數remainder為1，以儲存每次迭代中N留下的餘數，並將itr宣告為1以計算迭代次數。

• 步驟2 − 使用while迴圈，直到remainder變為0。

• 步驟3 − 在每一步，更新remainder並將itr加1。

• 步驟4 − 一旦remainder等於0，返回itr。

讓我們嘗試對N=13使用這種方法。

因為我們在while迴圈之前將remainder和itr宣告為1。

現在：

• 在第一次迭代中，remainder將為(remainder*10+1)%N，結果為11。remainder=11，itr=2。按照相同的演算法進行，直到remainder變為0。

• 在第二次迭代中，remainder=7，itr=3

• 在第三次迭代中，remainder=6，itr=4

• 在第四次迭代中，remainder=9，itr=5

• 在第五次迭代中，remainder=0，itr=6。

由於remainder變為0，我們將返回itr，即6，這就是所需的輸出。

方法

以下是上述方法在C++中的實現：

#include <iostream>
#include<bits/stdc++.h>

using namespace std;

//function to calculate no of ones in smallest repunit
int numberOfones(int N){  
   int remainder=1;
   
   int itr=1; // to store no of iterations
   
   while(remainder!=0){
      //update remainder
      remainder=(remainder*10 + 1)% N;
   
      itr++; //increase itr by 1 to get number of 1's in repunit
   }
   
   return itr;
}
int main(){
   int N=23;
   cout<<numberOfones(N);
   return 0;
}

輸出

22

能被23整除的最小迴圈單位將包含22個1。

結論

在本文中，我們嘗試解決如何求解能被任何個位數為3的正整數N整除的最小迴圈單位中1的個數的問題。我希望本文能幫助你理解這個問題。