C++-এ একটি সেটের সাবসেটগুলোর GCD যেন একটি দিয়া হয় সেটির সংখ্যা গণনা

একটি অ্যারে ar দেওয়া আছে যাতে ধনাত্মক সংখ্যা আছে এবং একটি অ্যারে GCD[] যাতে জিসিডি মানগুলো আছে। লক্ষ্য হলো arr[]-এর এলিমেন্টগুলোর সাবসেটগুলোর মধ্যে কতটির জিসিডি GCD[]-এ দিয়ে থাকা মানগুলোর সাথে মিলে সেটি বের করা।

উদাহরণ ১

ইনপুট

arr[] = {10, 5, 6, 3}, GCD[] = {2, 3, 5}

আউটপুট

এক সেটের সাবসেটগুলোর GCD যেন একটি দিয়া হয় সেটির সংখ্যা: 1 2 2

ব্যাখ্যা

GCD ২ হয় এমন সাবসেট: [10, 6]। GCD ৩ হয় এমন সাবসেট: [3], [6,3]। GCD ৫ হয় এমন সাবসেট: [5], [10, 5]

উদাহরণ ২

ইনপুট

arr[] = {10, 21, 7, 8}, GCD[] = {2, 7, 5}

আউটপুট

এক সেটের সাবসেটগুলোর GCD যেন একটি দিয়া হয় সেটির সংখ্যা: 1 2 0

ব্যাখ্যা

GCD ২ হয় এমন সাবসেট: [10, 8]। GCD ৭ হয় এমন সাবসেট: [7], [21,7]। GCD ৫ হয় এমন সাবসেট নেই।

প্রয়োগ করা পদ্ধতি

এই পদ্ধতিতে একটি unordered_map um_1 ব্যবহার করা হয় arr[]-এর এলিমেন্টগুলোর ফ্রিকোয়েন্সি সংরক্ষণের জন্য এবং একই টাইপের um_2 দিয়ে দিয়ে যেসব সাবসেটের জিসিডি দেওয়া আছে সেটির সংখ্যা সংরক্ষণ করা হয়। arr[]-এর এলিমেন্টগুলোর মধ্যে সর্বোচ্চ মান count-এ নিন। এখন i=count থেকে i>=1 পর্যন্ত লুপ চালিয়ে বর্তমান জিসিডির জন্য সাবসেটের সংখ্যা বের করুন। এর জন্য um_1-এ i-এর গুণফলগুলো কাউন্ট করুন। যদি i-এর গুণফলগুলোর সংখ্যা total হয়, তবে জিসিডি i হয় এমন সাবসেটের সংখ্যা 2^total - 1 - temp। যেখানে temp হলো i-র চেয়ে বড় জিসিডি 가진 সাবসেটগুলোর সংখ্যা যারা i নয়।

arr[] এবং GCD[] দুটি অ্যারে নিন।
subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD) ফাংশনটি দুটি অ্যারে এবং তাদের দৈর্ঘ্য গ্রহণ করে ফলাফল রিটার্ন করে।
আরম্ভিক কাউন্ট ০ রাখুন।
for লুপ দিয়ে arr[] ট্রুভার্স করুন এবং count-কে সর্বোচ্চ মান হিসেবে আপডেট করুন এবং um_1[arr[i]]++ দিয়ে ফ্রিকোয়েন্সি আপডেট করুন।
for লুপ দিয়ে i=count থেকে i>=1 পর্যন্ত, total হিসেবে i-এর গুণফলগুলোর ফ্রিকোয়েন্সির যোগফল এবং temp=0 হিসেবে i-র চেয়ে বড় জিসিডি 가진 সাবসেটের সংখ্যা নিন।
আরেক for লুপ দিয়ে j=2 থেকে j*i <= count পর্যন্ত, total-এ um_1[j*i] এবং temp-এ um_2[j*i] যোগ করুন।
দুটি লুপ শেষে um_2[i] = (1< সেট করুন।


um_2[GCD[i]] প্রিন্ট করুন ফলাফল হিসেবে যাতে জিসিডি দেওয়া সাবসেটের কাউন্ট থাকে।



উদাহরণ কোড
#include<bits/stdc++.h> 
using namespace std; 

void subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD) {
    unordered_map<int, int> um_1, um_2; 
    int count = 0; 
    
    for (int i=0; i= 1; i--) {
        int temp = 0; 
        int total = um_1[i]; 
        
        for (int j = 2; j*i <= count; j++) {
            total += um_1[j*i]; 
            temp += um_2[j*i]; 
        } 
        
        um_2[i] = (1<

আউটপুট
উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি আসবে:
এক সেটের সাবসেটগুলোর GCD যেন একটি দিয়া হয় সেটির সংখ্যা: 2 1