मान लीजिए nums सरणी में n पूर्णांक दिए गए हैं। हमें ज्ञात करना है कि सरणी की संख्याएँ युग्मवार सहअभाज्य (pairwise coprime), समुच्चयवार सहअभाज्य (setwise coprime), या सहअभाज्य नहीं (not coprime) हैं।
- दो संख्याएँ nums[i] और nums[j] युग्मवार सहअभाज्य कहलाती हैं यदि gcd(nums[i], nums[j]) = 1। यह सरणी के हर संख्या युग्म के लिए लागू होना चाहिए जहाँ i < j।
- संख्याएँ समुच्चयवार सहअभाज्य कहलाती हैं यदि सभी संख्याओं का gcd 1 हो।
- यदि वे न तो युग्मवार और न ही समुच्चयवार सहअभाज्य हैं, तो हम कहते हैं कि वे सहअभाज्य नहीं हैं।
उदाहरण के लिए, यदि इनपुट है n = 4, nums = {7, 11, 13, 17}, तो आउटपुट होगा "The numbers are pairwise coprime"।
यदि हम सरणी में हर संख्या युग्म की जाँच करें, तो उनका gcd हमेशा 1 होगा।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
आकार 100 का सरणी fac 0 से आरंभ करें
आकार 100 का सरणी checkPrime 0 से आरंभ करें
gcdVal := 0
i := 0 से n-1 तक:
gcdVal := gcd(nums[i], gcdVal)
fac[nums[i]] बढ़ाएँ
यदि gcdVal == 1, तो:
pw := true
k := 2 से 99 तक:
यदि checkPrime[k] सत्य है, तो जारी रखें
c := 0
j := k से 99 तक k के चरणों में:
c := c + fac[j]
checkPrime[j] := true
pw := pw AND (c <= 1)
यदि pw सत्य है, तो:
प्रिंट करें "The numbers are pairwise coprime"
अन्यथा:
प्रिंट करें "The numbers are setwise coprime"
अन्यथा:
प्रिंट करें "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
