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 số lẻ trong một khoảng cho trước. Chúng ta sẽ tìm số lượng các số 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 = 3
Đầu ra
2
Giải thích
Numbers with exactly 3 divisors within the range 3 to 10 are 4 : divisors = 1, 2, 4 9 : divisors = 1, 3, 9
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, để k là một số lẻ (như mô tả trong bài toán), số đó phải là một hình vuông hoàn hảo. Vì vậy, chúng tôi sẽ đếm số ước chỉ cho số bình phương hoàn hảo (điều này sẽ tiết kiệm thời gian biên dịch). Và nếu số lượng ước bằng k, chúng ta sẽ thêm 1 vào số lượng.
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;
bool isPerfectSquare(int n) {
int s = sqrt(n);
return (s*s == n);
}
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 (isPerfectSquare(i))
if (countDivisors(i) == k)
numberCount++;
}
return numberCount;
}
int main() {
int a = 3, b = 10, k = 3;
cout<<"The count of numbers with K odd divisors is "<<countNumberKDivisors(a, b, k);
return 0;
} Đầu ra
The count of numbers with K odd divisors is 2