กำหนดจำนวน n หาความน่าจะเป็นที่ตัวหารเฉพาะ (proper divisor) ของ n จะเป็นจำนวนกำลังสองคู่ (even perfect square)
เช่น n = 36 ผลลัพธ์คือ 1/8 เพราะตัวหารเฉพาะของ 36 มี 8 ตัว {1,2,3,4,6,9,12,18} มีเพียง 4 ที่เป็นกำลังสองคู่
วิธีแก้ปัญหา
- ถ้า n mod 4 != 0 คืนค่า 0
- มิฉะนั้น
- nc := n, ptr := 2
- l := list ใหม่
- while ptr <= sqrt(nc)
- a := 0
- while nc mod ptr == 0
- a := a + 1
- nc := floor(nc / ptr)
- ถ้า a > 0: append a ลง l
- ptr := ptr + 1
- ถ้า nc > 1: append 1 ลง l
- k := l[0], d := k + 1, no := floor(k/2)
- สำหรับแต่ละ i ใน l[1:]
- d := d * (i + 1)
- no := no * (floor(i/2) + 1)
- d := d - 1
- ถ้า n เป็นกำลังสองสมบูรณ์: no := no - 1
- g := gcd(d, no)
- d := floor(d/g), no := floor(no/g)
- ถ้า no == 0: คืนค่า 0 มิฉะนั้น คืนค่าเศษส่วน no/d
ตัวอย่างโค้ด
from math import gcd
def solve(n):
if n % 4 != 0:
return 0
else:
nc = n
ptr = 2
l = []
while ptr <= nc ** 0.5:
a = 0
while nc % ptr == 0:
a += 1
nc = nc / ptr
if a > 0:
l += [a]
ptr += 1
if nc > 1:
l += [1]
k = l[0]
d = k + 1
no = int(k / 2)
for i in l[1:]:
d = d * (i + 1)
no *= int(i / 2) + 1
d = d - 1
if int(n ** 0.5) ** 2 == n:
no -= 1
g = gcd(d, no)
d = d // g
no = no // g
if no == 0:
return 0
else:
return str(no) + '/' + str(d)
n = 36
print(solve(n))Input
4, 27
Output
1/8
