C++ এ প্রদত্ত সংখ্যার সমান GCD সহ একটি সেটের উপসেটের সংখ্যা গণনা করুন

একটি অ্যারে দেওয়া হয়েছে, যার মধ্যে ধনাত্মক সংখ্যা রয়েছে এবং একটি অ্যারে GCD[] রয়েছে যাতে gcd মান রয়েছে। লক্ষ্য হল arr[] এর উপাদানগুলির উপসেটের সংখ্যা খুঁজে বের করা যাতে GCD[]-এ দেওয়া gcd মান রয়েছে।

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

ইনপুট

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

আউটপুট

প্রদত্ত সংখ্যার সমান GCD সহ একটি সেটের উপসেটের সংখ্যা হল:1 2 2

ব্যাখ্যা

2 এর সমান GCD সহ উপসেটগুলি হল [ 10, 6 ]। 3 এর সমান GCD সহ উপসেট হল [ 3 ], [ 6,3 ] 5 এর সমান GCD সহ উপসেট হল [ 5 ], [ 10, 5 ] 
ইনপুট
 
arr[] ={10, 21, 7, 8}, GCD[] ={2, 7, 5}
 
আউটপুট
 
প্রদত্ত সংখ্যার সমান GCD সহ একটি সেটের উপসেটের সংখ্যা হল:12 0
 
ব্যাখ্যা
 
2 এর সমান GCD সহ সাবসেট হল [ 10, 8 ]। 7 এর সমান GCD সহ উপসেট হল [ 7 ], [ 21,7 ] 5 এর সমান GCD সহ কোন উপসেট নেই।
 

 নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
 

 এই পদ্ধতিতে আমরা arr[] এর উপাদানগুলির ফ্রিকোয়েন্সি সংরক্ষণের জন্য একটি unordered_map um_1 এবং প্রদত্ত gcd সহ উপসেটের সংখ্যা সংরক্ষণের জন্য অনুরূপ মানচিত্র um_2 তৈরি করব। গণনা হিসাবে arr[] এর উপাদানগুলির মধ্যে সর্বাধিক মান নিন। এখন i=count থেকে i>=1 পর্যন্ত একটি লুপ চালান এবং বর্তমান gcd-এর জন্য উপসেটের সংখ্যা খুঁজুন। এর জন্য আমরা um_1 এ i এর গুণিতক সংখ্যা গণনা করব। যদি i এর গুণিতকের সংখ্যা মোট হয় তাহলে gcd i সহ উপসেটের সংখ্যা হল total2−1−temp. যেখানে temp হল সাবসেটের সংখ্যা যার gcd i এর থেকে বেশি কিন্তু i এর সমান নয়৷
 
 
 

 arr[] এবং GCD[] এর জন্য দুটি অ্যারে নিন।
 
 
 

 ফাংশন সাবসেট_GCD(int arr[], int size_arr, int GCD[], int size_GCD) উভয় অ্যারে এবং তাদের দৈর্ঘ্য নেয় এবং একটি প্রদত্ত সংখ্যার সমান GCD সহ একটি সেটের উপসেটের সংখ্যা প্রদান করে৷
 
 
 

 ফাংশন সাবসেট_GCD(int arr[], int size_arr, int GCD[], int size_GCD) উভয় অ্যারে এবং তাদের দৈর্ঘ্য নেয় এবং একটি প্রদত্ত সংখ্যার সমান GCD সহ একটি সেটের উপসেটের সংখ্যা প্রদান করে৷
 
 
 

 0 হিসাবে প্রাথমিক গণনা নিন।
 
 
 

 ট্রাভার্স arr[] লুপ ব্যবহার করে এবং সর্বাধিক মান হিসাবে আপডেট গণনা খুঁজুন এবং um_1[arr[i]]++ ব্যবহার করে ফ্রিকোয়েন্সি সহ um_1 আপডেট করুন।
 
 
 

 i=count থেকে i>=1 পর্যন্ত লুপ ব্যবহার করে, i এর গুণিতকগুলির ফ্রিকোয়েন্সির যোগফল হিসাবে মোট নিন এবং temp=0 উপসেটের সংখ্যা হিসাবে নিন যেগুলির gcd i এর থেকে বেশি কিন্তু i এর সমান নয়৷
 
 
 

 j=2 থেকে j*i<=count এ আবার যাত্রা করুন, মোটে um_1[j*i] যোগ করুন এবং temp-এ um_2[j*i] যোগ করুন।
 
 
 

 লুপের জন্য উভয়ের শেষে um_2[i] =(1<<মোট) − 1 − temp সেট করুন।
 
 
 

 প্রিন্ট করুন um_2[GCD[i]] ফলের অ্যারের জন্য যেগুলিতে GCD দেওয়া সহ উপসেটের সংখ্যা রয়েছে৷
 
 
 
উদাহরণ
 
#includeনেমস্পেস ব্যবহার করে std;void subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD){unordered_map um_1, um_2; int count =0; জন্য (int i=0; i=1; i−−){ int temp =0; int মোট =um_1[i]; জন্য (int j =2; j*i <=গণনা; j++){ মোট +=um_1[j*i]; temp +=um_2[j*i]; } um_2[i] =(1<<মোট) − 1 − temp; } cout<<"প্রদত্ত সংখ্যার সমান GCD সহ একটি সেটের উপসেটের সংখ্যা হল:"; জন্য (int i=0; i 
আউটপুট
 

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