数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学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等）编写此代码。希望本文对您有所帮助。
更新于：2021年11月29日
浏览量：111
广告