মনে করুন আমাদের কাছে nums নামের একটি পজিটিভ মান সম্বলিত অ্যারে আছে। আমাদের nums-এর সব নন-এম্পটি সাবসিকোয়েন্সের মধ্যে ভিন্ন 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], মোট ৪টি সংখ্যা।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
T := nums-এর সর্বোচ্চ + 1
nums := nums-এর সব ডISTINCT সংখ্যা ধারণকারী একটি নতুন সেট
ans := 0
x = 1 থেকে T-1 পর্যন্ত জন্য, করুন
g := 0
y = x থেকে T-1 পর্যন্ত, প্রতিটি স্টেপে x দিয়ে আপডেট করে, করুন
যদি y nums-এ থাকে, তবে
g := gcd(g, y)
যদি g == x হয়, তবে
লুপ থেকে বের হোন
যদি g == x হয়, তবে
ans := ans + 1
ans রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন
from math import gcd
def solve(nums):
T = max(nums) + 1
nums = set(nums)
ans = 0
for x in range(1, T):
g = 0
for y in range(x, T, x):
if y in nums:
g = gcd(g, y)
if g == x:
break
if g == x:
ans += 1
return ans
nums = [4,6,18]
print(solve(nums))
ইনপুট
[4,6,18]
আউটপুট
4
