最小循环单位中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的个数的问题。我希望本文能帮助你理解这个问题。