পাইথনে কো-প্রাইম জোড়া যাদের গুণফল x এবং যোগফল ১ থেকে n পর্যন্ত

একটি ফাংশন f(x) আছে যা এমন জোড়া (p, q) গণনা করে যেখানে:

• 1 < p <= q <= x
• p এবং q কো-প্রাইম (GCD = 1)
• p * q = x

১ থেকে n পর্যন্ত সব x এর জন্য f(x) এর যোগফল বের করতে হবে।

উদাহরণ

ইনপুট: 12

আউটপুট: 3

কারণ:

• x = 6: (2, 3) → f(6) = 1
• x = 10: (2, 5) → f(10) = 1
• x = 12: (3, 4) → f(12) = 1

সমাধান পদ্ধতি

1. count := 0
2. sqr := int(sqrt(n)) + 1
3. base = 2 থেকে sqr - 1 পর্যন্ত:
   • i = 1 থেকে min(base, n // base - base + 1) পর্যন্ত:
     • যদি gcd(base, i) != 1 হয়, কন্টিনিউ করুন।
     • count += (n - i * base) // (base * base)
4. count রিটার্ন করুন।

পাইথন ইমপ্লিমেন্টেশন

from math import sqrt, gcd

def solve(n):
    count = 0
    sqr = int(sqrt(n)) + 1
    for base in range(2, sqr):
        for i in range(1, min(base, n // base - base + 1)):
            if gcd(base, i) != 1:
                continue
            count += (n - i * base) // (base * base)
    return count

# টেস্ট
n = 12
print(solve(n))  # আউটপুট: 3

ইনপুট

12

আউটপুট

3