Cho ba số X, Y và N (để xác định khoảng [1, N]). Mục tiêu là tìm tất cả các số trong khoảng [1, N] có thể xây dựng chỉ bằng X và Y bất kỳ số lần nào.
Ví dụ nếu X=2 và Y=3. Số 6 có thể xây dựng bằng 2 ba lần (2+2+2) hoặc 3 hai lần (3+3). Tương tự 7 có thể xây dựng bằng 2 hai lần và 3 một lần (2+2+3).
Ta thực hiện bằng cách trừ X hoặc Y từ mỗi số từ 1 đến N. Nếu số cuối cùng giảm về 0 thì tăng biến đếm.
Hãy hiểu qua các ví dụ.
Đầu vào
N=10 X=4, Y=3
Đầu ra
Tổng số xây dựng được từ X & Y: 7
Giải thích
Các số xây dựng được từ 3 và 4: 3, 4, 6 (3+3), 7 (3+4), 8 (4+4), 9 (3+3+3), 10 (3+3+4)
Đầu vào
N=10 X=5, Y=4
Đầu ra
Tổng số xây dựng được từ X & Y: 5
Giải thích
Các số xây dựng được từ 4 và 5: 4, 5, 8(4+4), 9 (4+5), 10 (5+5)
Phương pháp sử dụng trong chương trình dưới đây
- Nhận ba số nguyên X, Y và N.
- Hàm
constructNums(int n, int x, int y)trả về số lượng số có thể xây dựng chỉ bằng x và y. - Khởi tạo biến count = 0 cho các số như vậy.
- Duyệt khoảng số bằng vòng lặp for. i=1 đến i<=n.
- Với mỗi số num=i, dùng vòng lặp while kiểm tra num>0,
- while(num%x==0) và num khác 0 thì trừ x khỏi nó.
- while(num%y==0) và num khác 0 thì trừ y khỏi nó.
- Nếu sau khi trừ x và y số không chia hết cho cả hai và lớn hơn cả hai. Trừ cả x và y khỏi nó.
- Nếu sau vòng lặp while bên ngoài kiểm tra num bằng 0. Nghĩa là x, y hoặc cả hai tạo được num. Tăng count.
- Sau tất cả vòng lặp count sẽ chứa tổng số.
- Trả về count làm kết quả.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int constructNums(int n, int x, int y) {
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while(num > 0) {
while((num % x) == 0 && num != 0)
num -= x;
while((num % y) == 0 && num != 0)
num -= y;
if (num > x && num > y)
num = num - x - y;
else
break;
}
if (num == 0) {
count++;
}
}
return count;
}
int main() {
int N = 20;
int X = 5, Y = 4;
cout << "Tổng số xây dựng được từ X & Y: " << constructNums(N, X, Y);
return 0;
}
Đầu ra
Nếu chạy mã trên sẽ cho kết quả sau:
Tổng số xây dựng được từ X & Y: 14