ปัญหา
กำหนดจำนวนเฉพาะตัวประกอบ (Prime Factors) pf ต้องสร้างจำนวน n ที่มี Prime Factors ≤ pf เพื่อให้ Nice Divisors สูงสุด Nice Divisor = ตัวหารที่หารด้วยทุก Prime Factor ของ n ลงตัว
ตัวอย่าง
pf = 5 → Output: 6
n = 200 = 2³ × 5² Prime Factors: [2,2,2,5,5] (5 ตัว)
Nice Divisors: [10,20,40,50,100,200] = 6 ตัว
ข้อสังเกตทางคณิตศาสตร์
Nice Divisors = ผลคูณของ (Exponent_i + 1) สำหรับ Prime Factors ที่แตกต่างกัน
เพื่อ Maximize ผลคูณภายใต้เงื่อนไข Sum of Exponents ≤ pf → แบ่ง pf เป็นผลรวมของจำนวนเต็มบวก ให้ผลคูณสูงสุด
คำตอบ: ใช้ 3 มากที่สุด (3+3+...+3) เหลือ 0,1,2
- เหลือ 0: 3^(pf/3)
- เหลือ 1: 3^((pf-4)/3) × 4 (เพราะ 3+1 → 2+2 ให้ผลคูณมากกว่า)
- เหลือ 2: 3^(pf/3) × 2
ตัวอย่างโค้ด
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: # r == 2
return pow(3, q, m) * 2 % m
pf = 5
print(solve(pf)) # 6ความซับซ้อน
- Time: O(log pf) จาก pow()
- Space: O(1)
