ค้นหาจำนวนบวก M เพื่อให้ gcd(N^M,N&M) เป็นค่าสูงสุดใน Python

สมมติว่าเรามีตัวเลข N เราต้องหาจำนวนบวก M โดยที่ gcd(N^M, N&M) มีค่ามากที่สุดและ m

ดังนั้นหากอินพุตเท่ากับ 20 เอาต์พุตจะเป็น 31

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

ถ้า bit_count(n) เหมือนกับ 0 แล้ว
- สำหรับฉันในช่วง 2 ถึง int(สแควร์รูทของ (n)) + 1 ทำ
  - ถ้า n mod i เหมือนกับ 0 แล้ว
    - คืนค่า int(n / i)
มิฉะนั้น
- ค่า :=0
- p :=
- dupn :=n
- ในขณะที่ n ไม่ใช่ศูนย์ ให้ทำ
  - ถ้า (n AND 1) เหมือนกับ 0 แล้ว
    - วาล :=วาล + p
  - p :=p * 2
  - n :=n>> 1
- ส่งคืน gcd(val XOR dupn, val AND 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))

ค้นหาจำนวนบวก M เพื่อให้ gcd(N^M,N&M) เป็นค่าสูงสุดใน Python

ตัวอย่าง

อินพุต

ผลลัพธ์