এই সমস্যায়, আমাদের তিনটি পূর্ণসংখ্যার মান দেওয়া হয়েছে, L, R, এবং k। আমাদের কাজ হল একটি নির্দিষ্ট পরিসরে K বিজোড় ভাজক সহ সংখ্যাগুলি খুঁজে বের করা। আমরা [L, R] পরিসরে সংখ্যার গণনা খুঁজে পাব যার ঠিক k ভাজক আছে।
আমরা 1 এবং সংখ্যা নিজেই একটি ভাজক হিসাবে গণনা করব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
a = 3, b = 10, k = 3
আউটপুট
2
ব্যাখ্যা
Numbers with exactly 3 divisors within the range 3 to 10 are 4 : divisors = 1, 2, 4 9 : divisors = 1, 3, 9
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল k ভাজক গণনা করে। সুতরাং, k একটি বিজোড় সংখ্যা হওয়ার জন্য (যেমন সমস্যায় চিত্রিত), সংখ্যাটিকে একটি নিখুঁত বর্গ হতে হবে। সুতরাং, আমরা শুধুমাত্র নিখুঁত বর্গ সংখ্যার জন্য ভাজকের সংখ্যা গণনা করব (এটি সংকলনের সময় বাঁচাবে)। এবং যদি k তে ভাজক গণনা করা হয়, তাহলে আমরা সংখ্যা গণনার সাথে 1 যোগ করব।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
