สมมติว่าเรามีตัวเลข 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
