Trong bài toán này, chúng ta có ba giá trị nguyên là L, R và k. Nhiệm vụ của chúng ta là tìm các số có K ước trong một phạm vi nhất định. Chúng ta sẽ tìm số đếm trong phạm vi [L, R] có đúng k ước số. Chúng tôi sẽ đếm số 1 và số chính nó như một ước số.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
a = 3, b = 10, k = 4
Đầu ra
2
Giải thích
Numbers with exactly 3 divisors within the range 3 to 10 are 6 : divisors = 1, 2, 3, 6 8 : divisors = 1, 2, 4, 8
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là đếm k ước số .. Vì vậy, chúng ta sẽ đếm số ước số cho tất cả các số trong phạm vi. Và nếu số lượng ước bằng k, chúng ta sẽ thêm 1 vào số đếm.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include<bits/stdc++.h>
using namespace std;
int countDivisors(int n) {
int divisors = 0;
for (int i=1; i<=sqrt(n)+1; i++) {
if (n%i==0) {
divisors++;
if (n/i != i)
divisors ++;
}
}
return divisors;
}
int countNumberKDivisors(int a,int b,int k) {
int numberCount = 0;
for (int i=a; i<=b; i++) {
if (countDivisors(i) == k)
numberCount++;
}
return numberCount;
}
int main() {
int a = 3, b = 10, k = 4;
cout<<"The count of numbers with "<<k<<" divisors is "<<countNumberKDivisors(a, b, k);
return 0;
} Đầu ra
The count of numbers with 4 divisors is 2