Python-এ শুধুমাত্র একটি সমাধান বিশিষ্ট রৈখিক সমীকরণের সহগ খুঁজে বের করার প্রোগ্রাম

মান লেট n হয়, আমাদের (a, b) জোড়া [a < b] কতটুকু আছে সেটা খুঁজে বের করতে হবে যাতে সমীকরণ a*x + b*y = n-র কমপক্ষে একটি সমাধান থাকে।

তাহলে, যদি ইনপুট হয় n = 4, তবে আউটপুট হবে ২ কারণ বৈধ জোড়াগুলো হল (1, 2) এবং (1, 3)।

এটি সমাধান করতে, আমরা নিচের পদক্ষেপগুলো অনুসরণ করব −

একটি ফাংশন divisors_gen() সংজ্ঞায়িত করুন। এটি n নিবে
divs := n+1 আকারের একটি লিস্ট অফ লিস্ট। এবং প্রতিটি ইনার লিস্ট ১ ধারণ করছে
divs[0] := শুধু ০ ধারণকারী একটি লিস্ট
i ২ থেকে n পর্যন্ত রেঞ্জে, করুন
- j ১ থেকে floor of (n / i) + 1 পর্যন্ত রেঞ্জে, করুন
  - i * j ইনডেক্সে i ইনসার্ট করুন
divs রিটার্ন করুন কিন্তু সব ইন্টারনাল লিস্ট রিভার্স করে
মেইন মেথড থেকে, নিচের কাজ করুন −
result := 0
d_cache := divisors_gen(n+1)
a ১ থেকে n - 1 পর্যন্ত রেঞ্জে, করুন
- i := 1
- s := একটি নতুন সেট
- যখন a*i < n, করুন
  - b := n - a*i
  - d_cache[b]-এ থাকা প্রতিটি d-এর জন্য, করুন
    - যদি d > a, তবে
      - যদি d s-তে না থাকে, তবে
        result := result + 1
    - অন্যথায়,
      - লুপ থেকে বের হোন
    - d কে সেট s-এ ইনসার্ট করুন
  - i := i + 1
result রিটার্ন করুন

উদাহরণ

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন −

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))