পাইথনে gcd(N^M, N&M) সর্বাধিক করার জন্য ধনাত্মক M খুঁজুন

ধরি আমাদের কাছে একটি সংখ্যা N আছে, আমাদের একটি ধনাত্মক সংখ্যা M খুঁজে বের করতে হবে যাতে gcd(N^M, N&M) যতটা সম্ভব বড় হয় এবং m < n। আমরা পাওয়া সবচেয়ে বড় gcd-টিও রিটার্ন করব।

উদাহরণ

ইনপুট: 20

আউটপুট: 31

সমাধানের ধাপসমূহ

যদি bit_count(n) == 0, তবে:
- i = 2 থেকে int(sqrt(n)) + 1 পর্যন্ত লুপ চালান
- যদি n % i == 0, তবে int(n / i) রিটার্ন করুন
অন্যথায়:
- val := 0, p := 1, dupn := n
- যখন n নন-জিরো:
  - যদি (n & 1) == 0, তবে val := val + p
  - p := p * 2
  - n := n >> 1
- gcd(val ^ dupn, val & dupn) রিটার্ন করুন
1 রিটার্ন করুন

পাইথন কোড উদাহরণ

from math import gcd, sqrt

def bit_count(n):
    if (n == 0):
        return 0
    else:
        return (((n & 1) == 0) + bit_count(n >> 1))

def maximum_gcd(n):
    if (bit_count(n) == 0):
        for i in range(2, int(sqrt(n)) + 1):
            if (n % i == 0):
                return int(n / i)
    else:
        val = 0
        p = 1
        dupn = n
        while (n):
            if ((n & 1) == 0):
                val += p
            p = p * 2
            n = n >> 1
        return gcd(val ^ dupn, val & dupn)
    return 1

n = 20
print(maximum_gcd(n))