使用 C++ 重复单位除法

在本文中，我们将讨论找到可被N整除的重复单元数。重复单元仅是1的重复数，设R(k)为重复单元，其中k是1的长度。E.gR(4)=1111.所以我们需要找到R(k)可以被N整除的k的最小数目，例如-

Input : N = 13 Output : k = 6 Explanation : R(6)i.e111111 is divisible by 13. Input : N = 31 Output : k = 15

寻找解决方案的方法

您可以通过检查从1开始的k的每个值来解决这个问题，其中R(k)可以被N整除。但是使用这个解决方案，我们不会发现N是否可以被的任何值整除R(k)。这会使程序过于复杂，甚至可能无法运行。

解决该程序的一种有效方法是，

检查N是否与10互质。

如果不是，则R(k)对于任何k值都不能被N整除。

如果是，则对于每个重复单元R(1)、R(2)、R(3)...等，计算R(i)和N的除法余数，所以将有n个余数。

为R(i)and找出相同的余数R(j)，其中R(i)和R(j)是两个重复单位，因此R(i)-R(j)将被N整除。

的aThe差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; //检查N是否与10互质。 if (N % 2 == 0 || N % 5 == 0){ k = 0; } else { int r = 1; int power = 1; //检查直到余数可以被N整除。 while (r % N != 0) { k++; power = power * 10 % N; r = (r + power) % N; } } cout << "k的值： "<< k; return 0; }输出结果k的值： 15

结论

在本文中，我们讨论了为找到k的值R(k)，其中R(k)重复单位可以被给定整除，N.We讨论了一种找到k值的乐观方法。我们还讨论了C++代码来解决这个问题。您可以使用任何其他语言（如Java、C、Python等）编写此代码。我们希望本文对您有所帮助。