মান লিজিয়ে, nums অ্যারেতে n টি পূর্ণসংখ্যা দেওয়া আছে। আমাদের লক্ষ্য হলো অ্যারেতে থাকা সংখ্যাগুলো পেয়ারওয়াইজ কো-প্রাইম, সেটওয়াইজ কো-প্রাইম, না কো-প্রাইম কিনা তা নির্ধারণ করা।
দুটি সংখ্যা nums[i] এবং nums[j] কে পেয়ারওয়াইজ কো-প্রাইম বলা হয় যদি gcd(nums[i], nums[j]) = 1। এটি অ্যারেতে থাকা সব সংখ্যা জোড়ার জন্য সত্য হতে হবে এবং i < j।
সংখ্যাগুলোকে সেটওয়াইজ কো-প্রাইম বলা হয় যদি gcd(সকল nums[i]) = 1।
যদি উভয়ই না হয়, তবে আমরা বলবো সংখ্যাগুলো কো-প্রাইম নয়।
যেমন, ইনপুট হলে n = 4, nums = {7, 11, 13, 17}, তবে আউটপুট হবে "The numbers are pairwise coprime"।
যদি আমরা অ্যারেতে থাকা প্রতিটি সংখ্যা জোড়া চেক করি, তবে তাদের gcd সবসময় ১ হবে।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
fac অ্যারে সংজ্ঞায়িত করুন আকার: ১০০, ০ দিয়ে আরম্ভ করা। checkPrime অ্যারে সংজ্ঞায়িত করুন আকার: ১০০, ০ দিয়ে আরম্ভ করা। gcdVal := 0 i := 0 থেকে n-1 পর্যন্ত: gcdVal := gcd(nums[i], gcdVal) fac[nums[i]] ১ বাড়িয়ে if gcdVal == 1, তবে: pw := true k := 2 থেকে ৯৯ পর্যন্ত: if checkPrime[k] নন-জিরো, তবে: continue c := 0 j := k থেকে ৯৯ পর্যন্ত, j := j + k: c := c + fac[j] checkPrime[j] := true pw := pw AND (c <= 1) if pw নন-জিরো, তবে: print("The numbers are pairwise coprime") অন্যথায়: print("The numbers are setwise coprime") অন্যথায়: print("The numbers are not coprime") উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; void solve(int n, int nums[]){ int fac[100] = {0}; bool checkPrime[100] = {0}; int gcdVal = 0; for(int i = 0; i < n ; i++) { gcdVal = __gcd(nums[i], gcdVal); ++fac[nums[i]]; } if(gcdVal == 1) { bool pw = true; for(int k = 2; k < 100; ++k) { if(checkPrime[k]) continue; int c = 0; for(int j = k; j < 100; j += k) { c += fac[j]; checkPrime[j] = true; } pw = pw && c <= 1; } if(pw) cout<< "The numbers are pairwise coprime"; else cout<< "The numbers are setwise coprime"; } else cout << "The numbers are not coprime"; } int main() { int n = 4, nums[] = {7, 11, 13, 17}; solve(n, nums); return 0; } ইনপুট
4, {7, 11, 13, 17}; আউটপুট
The numbers are pairwise coprime
