C++实现重复单位的可除性

本文将讨论如何查找能被N整除的重复单位的个数。重复单位是由多个1组成的重复数字，设R(k)为重复单位，其中k表示1的个数。例如，R(4) = 1111。因此，我们需要找到最小的k值，使得R(k)可以被N整除，例如：

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整除。
• R(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等）编写此代码。希望本文对您有所帮助。

Prateek Jangid

更新于：2021年11月29日

浏览量：111

开启您的职业生涯

完成课程获得认证

开始学习