숫자 n이 있다고 가정하고 n의 적절한 제수가 짝수 완전제곱수가 될 확률을 찾아야 합니다.
따라서 입력이 n =36과 같으면 36의 적절한 제수가 8개 있으므로 출력은 1/8이 됩니다. 이들은 {1,2,3,4,6,9,12,18}이며 그 중 하나의 숫자(4)만 완전제곱수이고 짝수입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n mod 4가 0과 같지 않으면
- 0을 반환
- 그렇지 않으면
- nc :=n, ptr :=2
- l :=새 목록
- 동안 ptr <=nc의 제곱근, do
- a :=0
- nc mod ptr이 0인 동안 do
- a :=a + 1
- nc :=(nc / ptr)의 바닥
- a> 0이면
- 목록에 추가 l
- ptr :=ptr + 1
- nc> 1이면 목록에 1을 추가합니다.
- k :=l[0]
- d :=k + 1
- no :=(k / 2)의 바닥
- l[인덱스 1에서 끝까지]의 각 i에 대해 다음을 수행합니다.
- d :=d *(i + 1)
- 아니요 :=아니요 * (i / 2) + 1의 바닥
- d :=d - 1
- n이 완전제곱수이면
- 아니요 :=아니요 - 1
- g :=d의 gcd 및 없음
- d :=d / g의 바닥
- no :=no / g의 바닥
- no가 0과 같으면
- 0을 반환
- 그렇지 않으면
- 숫자 없음/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