資料結構
網路
關係型資料庫管理系統 (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
廣告