Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมเพื่อเพิ่มจำนวนตัวหารที่ดีใน Python


สมมติว่าเรามีตัวเลข pf แทนจำนวนตัวประกอบเฉพาะ เราต้องสร้างจำนวนบวก n ซึ่งเป็นไปตามเงื่อนไขต่อไปนี้ -

  • จำนวนของตัวประกอบเฉพาะของ n (อาจจะหรืออาจจะไม่ชัดเจน) มีค่า pf สูงสุด

  • จำนวนตัวหารที่ดีของ n ถูกขยายให้ใหญ่สุด ดังที่เราทราบดีว่าตัวหารของ n นั้นดีเมื่อตัวประกอบเฉพาะของ n ทุกตัวหารลงตัว

เราต้องหาจำนวนตัวหารดีของ n หากคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนผลลัพธ์ modulo 10^9 + 7

ดังนั้น ถ้าอินพุตเป็นเหมือน pf =5 ผลลัพธ์จะเป็น 6 เพราะสำหรับ n =200 เรามีตัวประกอบเฉพาะ [2,2,2,5,5] และตัวหารที่ดีของมันคือ [10,20,40,50,100,200 ] ดังนั้น 6 ตัวหาร

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

  • ถ้า pf เหมือนกับ 1 แล้ว

    • กลับ 1

  • ม :=10^9 + 7

  • q :=ผลหารของ pf/3, r :=pf mod 3

  • ถ้า r เท่ากับ 0 แล้ว

    • คืนค่า 3^q mod m

  • มิฉะนั้นเมื่อ r เท่ากับ 1 แล้ว

    • ผลตอบแทน (3^(q-1) mod m)*4 mod m

  • มิฉะนั้น

    • กลับ (3^q mod m)*2 mod m

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

def solve(pf):
   if pf == 1:
      return 1
   m = 10** 9 + 7
   q, r = divmod(pf, 3)
   if r == 0:
      return pow(3, q, m)
   elif r == 1:
      return pow(3, q-1, m) * 4 % m
   else:
      return pow(3, q, m) * 2 % m

pf = 5
print(solve(pf))

อินพุต

5

ผลลัพธ์

6