Chúng tôi được cung cấp ba số X, Y và N (để xác định phạm vi [1, N]). Mục tiêu là tìm tất cả các số trong phạm vi [1, N] có thể được tạo chỉ bằng cách sử dụ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ể được xây dựng bằng cách sử dụng 2 ba lần (2 + 2 + 2) hoặc 3 hai lần (3 + 3). Tương tự, 7 có thể được xây dựng bằng cách sử dụng 2 lần và 3 một lần (2 + 2 + 3).
Chúng tôi sẽ thực hiện điều này bằng cách trừ X hoặc Y cho mỗi số từ 1 đến N. Nếu số cuối cùng giảm xuống 0 thì tính tăng dần.
Hãy cùng hiểu với các ví dụ.
Đầu vào
N=10 X=4, Y=3
Đầu ra
Total numbers constructed using X & Y only: 7
Giải thích
Numbers constructed by 3 and 4 only: 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
Total numbers constructed using X & Y only: 5
Giải thích
Numbers constructed by 4 and 5 only: 4, 5, 8(4+4), 9 (4+5), 10 (5+5)
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy ba số nguyên X, Y và N.
-
Hàm constructNums (int n, int x, int y) trả về số lượng các số chỉ có thể được tạo bằng cách sử dụng x và y.
-
Lấy số lượng biến ban đầu là 0 cho những số như vậy.
-
Dải số theo chiều ngang bằng cách sử dụng vòng lặp for. i =1 đến i <=n
-
Bây giờ đối với mỗi số num =i, sử dụng vòng lặp while kiểm tra xem num> 0,
-
while (num% x ==0) và num không phải là 0, trừ x khỏi nó.
-
while (num% y ==0) và num không phải 0 trừ y khỏi nó.
-
Nếu sau khi trừ đi số x và số y không chia hết cho cả hai và lớn hơn cả hai thì lấy số đó trừ cả x và y.
-
Nếu sau vòng lặp while bên ngoài kiểm tra xem num là 0. Nghĩa là x, y hoặc cả hai có thể tạo num. Số lượng tăng dần.
-
Ở cuối tất cả các vòng đếm sẽ có tổng số.
-
Trả về kết quả là số lượng.
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 <<"Total numbers constructed using X & Y only:"<<constructNums(N,X,Y);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Total numbers constructed using X & Y only:14