এই সমস্যায়, আমাদের তিনটি পূর্ণসংখ্যা মান L, R, এবং k দেওয়া আছে। আমাদের কাজ হল নির্দিষ্ট পরিসীমায় K সংখ্যক বিজোড় বিভাজক থাকা সংখ্যা খুঁজে বের করা। আমরা পরিসীমা [L, R] এ সংখ্যাগুলোর মধ্যে কতগুলোর ঠিক K সংখ্যক বিভাজক আছে তা গণনা করব। ১ এবং সংখ্যাটি নিজেরও ভাগসঙ্খ্যা হিসেবে গণনা করব।
উদাহরণ
ইনপুট
a = 3, b = 10, k = 3
আউটপুট
2
ব্যাখ্যা
৩ থেকে ১০ এর মধ্যে যেসব সংখ্যার ঠিক ৩টি বিভাজক আছে: ৪: বিভাজক = ১, ২, ৪ ৯: বিভাজক = ১, ৩, ৯
সমাধানের পদ্ধতি
এই সমস্যার সহজ সমাধান হল K সংখ্যক বিভাজক গণনা করা। যেহেতু K বিজোড় সংখ্যা (সমস্যা অনুযায়ী), তাই সংখ্যাটি একটি পারফেক্ট স্কয়ার হতে হবে। সুতরাং, আমরা শুধু পারফেক্ট স্কয়ার সংখ্যাগুলোর জন্য বিভাজক গণনা করব (এটি কম্পাইলেশন টাইম বাঁচাবে)। এবং যদি বিভাজক সংখ্যা K হয়, তবে সংখ্যা কাউন্টে ১ যোগ করব।
প্রোগ্রাম উদাহরণ
#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;
}
আউটপুট
The count of numbers with K odd divisors is 2
