এই সমস্যাতে, আমাদের একটি ধনাত্মক পূর্ণসংখ্যা N দেওয়া আছে। আমাদের কাজ হলো সংখ্যাটির পলাইটনেস (politeness) বের করা।
পলাইট নাম্বর (Polite Number) হলো এমন একটি সংখ্যা যাকে দুটি বা তার অধিক ক্রমাগত (consecutive) সংখ্যার যোগফল হিসেবে প্রকাশ করা যায়।
পলাইটনেস (Politeness of a number) হলো সেই সংখ্যাকে ক্রমাগত পূর্ণসংখ্যাগুলোর যোগফল হিসেবে কত প্রকারে প্রকাশ করা যায় তার সংখ্যা।
উদাহরণ দিয়ে সমস্যা বোঝা যাক,
ইনপুট
n = 5
আউটপুট
1
ব্যাখ্যা
2 + 3 = 5, একমাত্র ক্রমাগত যোগফল।
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হলো N পর্যন্ত সব ক্রমাগত সংখ্যা চেক করা এবং যদি তাদের যোগফল N-এর সমান হয়, তবে কাউন্ট বাড়ানো যা হলো সংখ্যাটির পলাইটনেস।
এটি দক্ষ সমাধান নয়। একটি জটিল কিন্তু দক্ষ সমাধান হলো ফ্যাক্টরাইজেশন (factorization) ব্যবহার করা। পলাইটনেসের সূত্র হচ্ছে বিজোড় গুণনীয়কগুলোর (odd factors) কাউন্টের গুণফল:
যদি সংখ্যাটি নিচের রূপে প্রকাশ করা যায়: N = a^x * b^y * c^z... তবে Politeness = [(x + 1)*(y + 1)*(z + 1)...] - 1
সমাধান কোড:
উদাহরণ
#include <iostream>
using namespace std;
int calcPolitenessNumber(int n){
int politeness = 1;
while (n % 2 == 0)
n /= 2;
for (int i = 3; i * i <= n; i += 2) {
int divCount = 0;
while (n % i == 0) {
n /= i;
++divCount;
}
politeness *= divCount + 1;
}
if (n > 2)
politeness *= 2;
return (politeness - 1);
}
int main(){
int n = 13;
cout<<"Politeness of "<<n<<" is "<<calcPolitenessNumber(n);
return 0;
}
আউটপুট
Politeness of 13 is 1
