Trong bài viết này, ta sẽ thảo luận tìm số đơn vị lặp lại chia hết cho N. Đơn vị lặp lại là các số lặp lại chỉ chứa chữ số 1, Gọi R(k) là đơn vị lặp lại với k là độ dài của các số 1. Vd R(4) = 1111. Vì vậy ta cần tìm số k nhỏ nhất sao cho R(k) chia hết cho N, ví dụ −
Input : N = 13 Output : k = 6 Giải thích : R(6) tức 111111 chia hết cho 13. Input : N = 31 Output : k = 15
Phương pháp tìm giải pháp
Bạn có thể tiếp cận bài toán bằng cách kiểm tra từng giá trị k bắt đầu từ 1 nơi R(k) chia hết cho N. Nhưng với giải pháp này, ta sẽ không biết liệu N có chia hết cho bất kỳ giá trị R(k) nào. Điều này sẽ làm chương trình quá phức tạp và có thể không hoạt động.
Một phương pháp hiệu quả cho giải pháp chương trình này là,
- Kiểm tra xem N có nguyên tố cùng nhau 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ị k nào.
- Nếu CÓ, thì với mỗi đơn vị lặp lại R(1), R(2), R(3)... Tính phần dư của phép chia R(i) cho N, sẽ có n số phần dư.
- Tìm các giá trị phần dư giống nhau cho R(i) và R(j), với R(i) và R(j) là hai đơn vị lặp lại sao cho R(i) - R(j) sẽ chia hết cho N.
- Hiệu của R(i) và R(j) sẽ là đơn vị lặp lại nhân với lũy thừa của 10, Nhưng 10 và N nguyên tố cùng nhau, nên 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; // kiểm tra nếu N nguyên tố cùng nhau với 10. if (N % 2 == 0 || N % 5 == 0){ k = 0; } else { int r = 1; int power = 1; // kiểm tra cho đến khi phần dư chia hết cho N. while (r % N != 0) { k++; power = power * 10 % N; r = (r + power) % N; } } cout << "Value for k : "<< k; return 0; } Kết quả
Value for k : 15
Kết luận
Trong bài viết này, ta thảo luận tìm giá trị k cho R(k), với R(k) là đơn vị lặp lại chia hết cho N cho trước. Ta thảo luận cách lạc quan để tìm giá trị k. Ta cũng thảo luận mã C++ để giải bài toán. 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. Hy vọng bạn thấy bài viết hữu ích.