C++-এ পেয়ার কাউন্ট: ১ থেকে a ও ১ থেকে b-র যোগফল N-এ বিভাজ্য

তিনটি পূর্ণসংখ্যা a, b, n দেওয়া আছে। ১ থেকে a পর্যন্ত এবং ১ থেকে b পর্যন্ত সংখ্যা দিয়ে বने যোড়া (x,y) এর যোগফল n-এ বিভাজ্য কতগুলো তা বের করুন।

উদাহরণ

a=2, b=3, n=2

যোড়াগুলো: (1,1)=2✓, (1,2)=3✗, (1,3)=4✓, (2,1)=3✗, (2,2)=4✓, (2,3)=5✗

আউটপুট: 3

অপ্টিমাইজড পদ্ধতি (O(n))

প্রতিটি i = 1..a এর জন্য, j = 1..b যাতে (i+j)%n==0। অর্থাৎ j ≡ -i (mod n)। প্রতিটি মডুলো ক্লাসের ফ্রিকোয়েন্সি গণনা করে O(n)-এ সমাধান সম্ভব।

C++ বাস্তবায়ন (সিম্পল O(a×b))

#include <iostream>
using namespace std;

int Pair_a_b(int a, int b, int n) {
    int count = 0;
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            if ((i + j) % n == 0)
                count++;
    return count;
}

int main() {
    int a = 2, b = 20, n = 4;
    cout << "Count: " << Pair_a_b(a, b, n);
    return 0;
}

অপ্টিমাইজড সংস্করণ (O(n))

int Pair_a_b_fast(int a, int b, int n) {
    vector cntA(n, 0), cntB(n, 0);
    for (int i = 1; i <= a; i++) cntA[i % n]++;
    for (int j = 1; j <= b; j++) cntB[j % n]++;
    
    long long ans = 0;
    for (int r = 0; r < n; r++) {
        int need = (n - r) % n;
        ans += cntA[r] * cntB[need];
    }
    return ans;
}