สมมติว่าเรามีตัวเลข n เราต้องหาความน่าจะเป็นที่ตัวหารแท้ของ n จะเป็นกำลังสองสมบูรณ์คู่
ดังนั้น หากอินพุตเท่ากับ n =36 ผลลัพธ์จะเป็น 1/8 เนื่องจากมีตัวหารถูกต้องแปดตัวของ 36 ตัวเหล่านี้คือ {1,2,3,4,6,9,12,18} และในนั้น มีเพียงตัวเลขเดียว (4) ที่เป็นกำลังสองสมบูรณ์และคู่
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ถ้า n mod 4 ไม่เหมือนกับ 0 แล้ว
- คืน 0
- มิฉะนั้น
- nc :=n, ptr :=2
- l :=รายการใหม่
- ในขณะที่ ptr <=รากที่สองของ nc ทำ
- a :=0
- ในขณะที่ nc mod ptr เหมือนกับ 0, do
- a :=a + 1
- nc :=ชั้นของ (nc / ptr)
- ถ้า a> 0 แล้ว
- เพิ่ม a ลงในรายการ l
- ptr :=ptr + 1
- ถ้า nc> 1 ให้ผนวก 1 ลงในรายการ l
- k :=l[0]
- d :=k + 1
- ไม่ :=ชั้นของ (k / 2)
- สำหรับแต่ละ i ใน l[จากดัชนี 1 ถึงจุดสิ้นสุด] ทำ
- d :=d *(i + 1)
- ไม่ :=ไม่ * ชั้นของ (i / 2) + 1
- d :=d - 1
- ถ้า n เป็นกำลังสองสมบูรณ์แล้ว
- ไม่ :=ไม่ - 1
- g :=gcd ของ d และ no
- d :=ชั้นของ d / g
- ไม่ :=ชั้นไม่มี / 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)) อินพุต
4, 27
ผลลัพธ์
1/8
