C++-এ N কে ১ করে কমাতে সর্বোচ্চ অপারেশন সংখ্যা (N = P!/Q!)

কনসেপ্ট

দুটি সংখ্যা P এবং Q দেওয়া আছে (P এবং Q ১০⁶ পর্যন্ত হতে পারে) যারা মিলে N = (P!/Q!) তৈরি করে। লক্ষ্য হল N কে ১ করে কমাতে সর্বোচ্চ সংখ্যক অপারেশন করা। প্রতিটি অপারেশনে N কে N/X দিয়ে প্রতিস্থাপন করা যায় যদি N, X দ্বারা বিভাজ্য হয়। সর্বোচ্চ কতগুলো অপারেশন করা সম্ভব তা নির্ণয় করুন।

ইনপুট ১

A = 7, B = 4

আউটপুট ১

N = ২১০ এবং এর अभাজ্য ভাগফল: ২, ৩, ৫, ৭

ইনপুট ২

A = 3, B = 1

আউটপুট ২

N = ৬ এবং এর अभাজ্য ভাগফল: ২, ৩।

পদ্ধতি

P!/Q!-এর ফ্যাক্টরাইজেশন (Q+1)×(Q+2)×...×P সংখ্যাগুলোর ফ্যাক্টরাইজেশনের সমান। অপারেশনের সংখ্যা সর্বোচ্চ হবে যদি N কে শুধু তার অভাজ্য গুণনীয়ক দ্বারা ভাগ করা হয়। অর্থাৎ N-এর অভাজ্য গুণনীয়কগুলোর সংখ্যা (ডুপ্লিকেট সহ) গণনা করতে হবে।

২ থেকে ১০০০০০০ পর্যন্ত প্রতিটি সংখ্যার অভাজ্য গুণনীয়ক গণনা করতে 'এরাটോস্থেনিসের সিফ' (Sieve of Eratosthenes) ব্যবহার করুন। তারপর প্রিফিক্স সম (prefix sum) অ্যারে তৈরি করে [P, Q] интерভালের যোগফল দ্রুত বের করুন।

উদাহরণ (C++ কোড)

// CPP প্রোগ্রাম: সর্বোচ্চ মুভ সংখ্যা খুঁজে বের করার জন্য
#include <bits/stdc++.h>
using namespace std;
#define N 1000005

// প্রতিটি সংখ্যার অভাজ্য গুণনীয়কের সংখ্যা সংরক্ষণ
int primeFactors1[N];

// অভাজ্য গুণনীয়ক গণনা করার ফাংশন
void findPrimeFactors() {
    for (int a = 2; a < N; a++)
        // যদি a অভাজ্য হয়
        if (primeFactors1[a] == 0)
            for (int b = a; b < N; b += a)
                // পূর্ববর্তী গুণিতক থেকে এক বেড়িয়ে মান বাড়ান
                primeFactors1[b] = primeFactors1[b / a] + 1;
    // প্রিফিক্স সম তৈরি (মাল্টিপল টেস্ট কেসের জন্য সহায়ক)
    for (int a = 1; a < N; a++)
        primeFactors1[a] += primeFactors1[a - 1];
}

// ড্রাইভার কোড
int main() {
    // primeFactors1 অ্যারে তৈরি
    findPrimeFactors();
    int P = 7, Q = 4;
    // প্রয়োজনীয় উত্তর
    cout << primeFactors1[P] - primeFactors1[Q];
    return 0;
}