C++-এ GCD ১ হওয়ালা সাবসিকোয়েন্স গণনা

একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে। যেসব সাবসিকোয়েন্সের GCD (সর্বোচ্চ সাধারণ ভাজক) ১, তাদের সংখ্যা গণনা করুন।

উদাহরণ

ইনপুট: [3, 4, 8, 16]

আউটপুট: 7

সাবসিকোয়েন্স: (3,4), (3,8), (3,16), (4,3), (8,3), (16,3), (3,4,8)

দ্রষ্টব্য: প্রদত্ত কোডে ত্রুটি আছে

প্রদত্ত কোডে ডাবল লুপ ব্যবহার করা হয়েছে যা i এবং j এর সব জোড়া যাচাই করে, কিন্তু সাবসিকোয়েন্সের জন্য এটি সঠিক নয়। সাবসিকোয়েন্সের অর্ডার মেইনটেইন করতে হয়।

সঠিক পদ্ধতি: ইনক্লুশন-এক্সক্লুশন / DP

প্রতিটি সম্ভাব্য GCD মান (1 থেকে maxElement) এর জন্য সাবসিকোয়েন্স গণনা করুন।
মবিয়াস ফাংশন বা DP ব্যবহার করে GCD=১ এর সংখ্যা বের করুন।

C++ বাস্তবায়ন (অপ্টিমাইজড)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9+7;
int solve(vector& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    vector freq(maxVal + 1, 0);
    for (int x : arr) freq[x]++;
    
    vector dp(maxVal + 1, 0);
    for (int g = maxVal; g >= 1; g--) {
        int cnt = 0;
        for (int m = g; m <= maxVal; m += g)
            cnt += freq[m];
        if (cnt == 0) continue;
        dp[g] = (1LL << cnt) - 1; // 2^cnt - 1 non-empty subsets
        for (int m = 2*g; m <= maxVal; m += g)
            dp[g] = (dp[g] - dp[m] + MOD) % MOD;
    }
    return dp[1];
}

সম্পূর্ণ উদাহরণ

int main() {
    vector arr = {3, 4, 8, 16};
    cout << solve(arr); // Output: 7
    return 0;
}