Trong bài này, chúng ta sẽ thảo luận về việc tìm số đơn vị lặp lại chia hết cho N. Đơn vị lặp là số lặp lại của 1 duy nhất, Gọi R (k) là đơn vị lặp với k là độ dài của 1’s. Ví dụ:R (4) =1111. Vì vậy, chúng ta cần tìm số k nhỏ nhất để R (k) chia hết cho N, chẳng hạn -
Input : N = 13 Output : k = 6 Explanation : R(6) i.e 111111 is divisible by 13. Input : N = 31 Output : k = 15
Phương pháp tiếp cận để tìm ra giải pháp
Bạn có thể tiếp cận bài toán này bằng cách kiểm tra từng giá trị của k bắt đầu từ 1 trong đó R (k) chia hết cho N. Nhưng với giải pháp này, chúng ta sẽ không tìm thấy liệu N có chia hết cho bất kỳ giá trị nào của R (k) hay không. Điều này sẽ làm cho chương trình quá phức tạp và có thể không hoạt động.
Phương pháp Tiếp cận Hiệu quả cho giải pháp của chương trình này là
- Kiểm tra xem N có đúng với 10 không.
- Nếu KHÔNG, thì R (k) sẽ không chia hết cho N với bất kỳ giá trị nào của k.
- Nếu CÓ, thì với mỗi đơn vị lặp lại R (1), R (2), R (3) ... và như vậy, Hãy tính phần còn lại của phép chia R (i) và N, Vậy sẽ có n số phần còn lại.
- Tìm các giá trị còn lại giống nhau của R (i) và R (j), trong đó R (i) và R (j) là hai đơn vị lặp lại sao cho R (i) - R (j) chia hết cho N.
- a Sự khác biệt của R (i) và R (j) sẽ là đơn vị lặp lại nhân với một số lũy thừa của 10, Nhưng 10 và N tương đối nguyên tố, vì vậy R (k) sẽ chia hết cho N.
Ví dụ
#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;
}
Đầu ra
Value for k : 15
Kết luận
Trong bài này, chúng tôi thảo luận về việc tìm giá trị của k đối với R (k), trong đó R (k) là các đơn vị lặp lại chia hết cho N. Chúng tôi đã thảo luận một cách lạc quan để tìm giá trị của k. Chúng tôi cũng đã thảo luận về mã C ++ để giải quyết vấn đề này. Bạn có thể viết mã này bằng bất kỳ ngôn ngữ nào khác như Java, C, Python, v.v. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.