ধরুন আমাদের কাছে ধনাত্মক মান সহ একটি অ্যারে সংখ্যা রয়েছে। সংখ্যার সমস্ত অ-খালি অনুসৃতির মধ্যে আমাদের বিভিন্ন GCD-এর সংখ্যা খুঁজে বের করতে হবে। আমরা জানি যে সংখ্যার ক্রমটির GCD হল সবচেয়ে বড় মান যা অনুক্রমের সমস্ত সংখ্যাকে সমানভাবে ভাগ করে।
সুতরাং, যদি ইনপুটটি nums =[4,6,18] এর মত হয়, তাহলে আউটপুট হবে 4 কারণ gcd([4]) =4, gcd([6]) =6, gcd([18]) =18 gcd([4,6]) =2, gcd([4,18]) =2, gcd([6,18]) =6, gcd([4,6,18]) =2 তাই সমস্ত সংখ্যা হল [ 4,6,18,2], 4টি সংখ্যা আছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
T :=সর্বাধিক সংখ্যা + 1
-
nums :=একটি নতুন সেট যাতে সমস্ত স্বতন্ত্র সংখ্যার সংখ্যা রয়েছে
-
উত্তর :=0
-
1 থেকে T - 1 এর মধ্যে x এর জন্য, করুন
-
g :=0
-
x থেকে T - 1 পরিসরে y এর জন্য, প্রতিটি ধাপে x দ্বারা আপডেট করুন, করুন
-
যদি y সংখ্যায় থাকে, তাহলে
-
g :=gcd(g, y)
-
-
যদি g x এর মত হয়, তাহলে
-
লুপস থেকে বেরিয়ে আসা
-
-
-
যদি g x এর মত হয়, তাহলে
-
ans :=ans + 1
-
-
-
উত্তর ফেরত দিন
উদাহরণ
আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি
গণিত আমদানি থেকে gcddef সমাধান(সংখ্যা):T =সর্বোচ্চ(সংখ্যা) + 1 সংখ্যা =সেট(সংখ্যা) উত্তর =0 পরিসরে x এর জন্য (1, T):g =0 পরিসরে y এর জন্য (x, T) , x):যদি y সংখ্যায়:g =gcd(g, y) যদি g ==x:break if g ==x:ans +=1 return ansnums =[4,6,18]print(solve(nums) )ইনপুট
[4,6,18]
আউটপুট
4
