Chương trình tối đa hóa số lượng ước số đẹp trong Python

Giả sử chúng ta có một số pf đại diện cho một số thừa số nguyên tố. Ta phải lập một số dương n thỏa mãn các điều kiện sau -

• Số thừa số nguyên tố của n (có thể khác nhau hoặc không) nhiều nhất là pf.

• Số ước số đẹp của n là cực đại. Như chúng ta biết một ước số của n là tốt khi nó chia hết cho mọi thừa số nguyên tố của n.

Chúng ta phải tìm số ước tốt đẹp của n. Nếu câu trả lời quá lớn thì trả về kết quả modulo 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là pf =5, thì đầu ra sẽ là 6 vì với n =200, chúng ta có các thừa số nguyên tố [2,2,2,5,5] và các ước số đẹp của nó là [10,20,40,50,100,200 ] 6 ước số.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu pf giống 1 thì

  • trả lại 1

• m:=10 ^ 9 + 7

• q:=thương số của pf / 3, r:=pf mod 3

• nếu r giống 0 thì

  • trả về 3 ^ q mod m

• ngược lại khi r giống 1 thì

  • return (3 ^ (q-1) mod m) * 4 mod m

• nếu không,

  • return (3 ^ q mod m) * 2 mod m

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn

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

Đầu vào

5

Đầu ra

6