ধরুন আমাদের একটি মান n আছে, আমাদের জোড়ার সংখ্যা খুঁজে বের করতে হবে (a, b) [a
সুতরাং, যদি ইনপুট n =4 এর মত হয়, তাহলে আউটপুট হবে 2 কারণ বৈধ জোড়া হল (1, 2) এবং (1, 3)।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন divisors_gen() সংজ্ঞায়িত করুন। এটি n লাগবে
- divs :=n+1 আকারের তালিকার একটি তালিকা। এবং প্রতিটি অভ্যন্তরীণ তালিকা 1 ধরে আছে
- divs[0] :=শুধুমাত্র একটি উপাদান 0 সহ একটি তালিকা
- 2 থেকে n রেঞ্জের i জন্য, করুন
- j এর জন্য রেঞ্জ 1 থেকে (n / i) + 1 এর ফ্লোর, করুন
- সূচীতে তালিকার শেষে i ঢোকান [i * j]
- j এর জন্য রেঞ্জ 1 থেকে (n / i) + 1 এর ফ্লোর, করুন
- ডিভ ফেরত দিন কিন্তু সমস্ত অভ্যন্তরীণ তালিকা উল্টে দিন
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
- ফলাফল :=0
- d_cache :=divisors_gen(n+1)
- 1 থেকে n - 1 এর রেঞ্জের জন্য, করুন
- i :=1
- s :=একটি নতুন সেট
- যখন a*i
- b :=n - a*i
- d_cache[b]-এ প্রতিটি d-এর জন্য, করুন
- যদি d> a, তারপর
- যদি s-এ d না থাকে, তাহলে
- ফলাফল :=ফলাফল + 1
- যদি s-এ d না থাকে, তাহলে
- অন্যথায়,
- লুপ থেকে বেরিয়ে আসুন
- s সেটে d ঢোকান
- i :=i + 1
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def divisors_gen(n): divs = [[1] for x in range(0, n + 1)] divs[0] = [0] for i in range(2, n + 1): for j in range(1, n // i + 1): divs[i * j].append(i) return [i[::-1] for i in divs] def solve(n): result = 0 d_cache = divisors_gen(n+1) for a in range(1, n): i = 1 s = set([]) while a*i < n: b = n - a*i for d in d_cache[b]: if d > a: if d not in s: result += 1 else: break s.add(d) i += 1 return result n = 4 print(solve(n))
ইনপুট
4
আউটপুট
2