কনসেপ্ট
একটি পূর্ণসংখ্যার অ্যারে দেওয়া আছে। এমন একটি পূর্ণসংখ্যা B খুঁজে বের করুন যা ঠিক একটি উপাদান বাদে সব উপাদানকে ভাগ করে। সব উপাদানের GCD 1 নয়।
ইনপুট ১
arr[] = {8, 16, 4, 24}
আউটপুট ১
8
৮, ১৬ এবং ২৪ কে ভাগ করে, ৪ কে ভাগ করে না।
ইনপুট ২
arr[] = {50, 15, 40, 41}
আউটপুট ২
5
৫, ১৫ এবং ৪০ কে ভাগ করে, ৪১ কে ভাগ করে না।
পদ্ধতি
প্রিফিক্স GCD অ্যারে A এবং সাফিক্স GCD অ্যারে C বানান। A[i] = 0..i পর্যন্ত GCD, C[i] = i..n-1 পর্যন্ত GCD। প্রতিটি i-এর জন্য GCD(A[i-1], C[i+1]) নির্ণয় করুন। যদি এটি a[i]-কে ভাগ না করে তবে সেটিই উত্তর।
উদাহরণ (C++ কোড)
// C++: ঠিক একটি বাদে সব উপাদানের বিভাজক
#include <bits/stdc++.h>
using namespace std;
int getDivisor1(int a1[], int n1) {
if (n1==1) return a1[0]+1;
int A[n1], C[n1];
A[0]=a1[0];
for(int i=1;i=0;i--) C[i]=__gcd(C[i+1],a1[i]);
for(int i=0;i
আউটপুট
5
