게임 쇼에서 원으로 배열된 2n개의 방이 있다고 가정합니다. 방 중 하나에는 참가자가 수집해야 하는 상품이 있습니다. 방의 번호는 1, 2, 3,...., n, -n, -(n - 1),...., -1입니다. 시계 방향으로. 각 방에는 문이 있고 그 문으로 다른 방을 방문할 수 있습니다. 모든 문에는 x 표시가 있습니다. 이는 다른 방이 현재 방에서 x 거리에 있음을 의미합니다. x 값이 양수이면 해당 방에서 시계 방향으로 x번째 방으로 문이 열립니다. x의 값이 음수이면 방이 시계 반대 방향으로 x번째 방으로 열립니다. 경품을 보관할 수 있는 방의 수를 알아내야 하고 참가자들이 경품을 찾는 데 어려움을 겪습니다.
따라서 입력이 input_array =[[4, 2]]와 같으면 출력은 [2]
가 됩니다.입력에는 두 개의 값이 있습니다. 첫 번째 값은 방 수의 절반인 n이고 두 번째 값은 참가자가 상품을 찾기 시작하는 방 번호입니다. 여기에는 2x4 =8개의 방이 있으며 참가자는 시계 방향으로 두 번째 방부터 상품을 찾기 시작합니다. 방은 시계 방향으로 1, 2, 3, 4, -4, -3, -2, -1로 번호가 매겨집니다. 참가자는 2, -4, -1, 1, 3, -2, -1, 1, 3, -2, ...와 같은 방식으로 방을 방문하기 시작합니다. 따라서 방 4와 -3은 방문했을 때 이 두 방 중 하나에 상품이 숨겨져 있으면 참가자가 찾을 수 없습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- prime_num_find() 함수를 정의합니다. n
- 이 걸립니다.
-
p_nums :=값 2로 초기화된 새 목록
-
check :=요소의 바이트 표현을 포함하는 새 목록
-
-
범위 3에서 n의 값에 대해 2만큼 증가, 수행
- check[value]가 0이 아니면
- 다음 반복으로 이동
- p_nums 끝에 값 삽입
- 범위 3 * 값에서 n까지의 i에 대해 각 단계에서 2 * 값으로 업데이트, do
- 체크[i] :=1
- p_nums 반환
- check[value]가 0이 아니면
- factor_finder() 함수를 정의합니다. 이것은 p
- 이 걸릴 것입니다
- p_nums :=prime_num_find(45000)
- f_nums :=새 지도
- p_nums의 각 값에 대해 다음을 수행합니다.
- 값 * 값> p가 0이 아니면
- 루프에서 나오다
- p mod 값이 0일 때 do
- p :=(p / 값)의 하한값
- 값이 f_nums에 있으면
- f_nums[값] :=f_nums[값] + 1
- 기타,
- f_nums[값] :=0
- 값 * 값> p가 0이 아니면
- p>
1이면
- f_nums[p] :=1
- 반환 f_nums
- euler_func() 함수를 정의합니다. 이것은 p
- 이 걸릴 것입니다
- f_nums :=factor_finder(p)
- t_value :=1
- f_nums의 각 값에 대해 다음을 수행합니다.
- t_value :=t_value * ((값-1) * 값^(f_nums[값] - 1))
- t_value 반환
- t_value :=t_value * ((값-1) * 값^(f_nums[값] - 1))
- 주요 함수/메서드에서 다음을 수행합니다. -
- 출력:=새 목록
- input_array의 각 항목에 대해 다음을 수행합니다.
- p :=항목[0]
- q :=항목[1]
- r :=2 * p + 1
- r :=(r / (r, q mod r)의 gcd 값)의 하한값
- t_value:=euler_func(r)
- factor_finder(t_value)의 각 값에 대해 다음을 수행합니다.
- t_value mod 값이 0이고 (2 ^(t_value/value) mod r의 floor 값)이 1인 동안 do
- t_value :=(t_value / 값)의 하한값
- t_value mod 값이 0이고 (2 ^(t_value/value) mod r의 floor 값)이 1인 동안 do
- 2 * p - 출력 끝에 t_value 삽입
- 반환 출력
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
import math
def prime_num_find(n):
p_nums = [2]
check = bytearray(n)
for value in range(3, n, 2):
if check[value]:
continue
p_nums.append(value)
for i in range(3 * value, n, 2 * value):
check[i] = 1
return p_nums
def factor_finder(p):
p_nums = prime_num_find(45000)
f_nums = {}
for value in p_nums:
if value * value > p:
break
while p % value == 0:
p //= value
f_nums[value] = f_nums.get(value,0) + 1
if p > 1:
f_nums[p] = 1
return f_nums
def euler_func(p):
f_nums = factor_finder(p)
t_value = 1
for value in f_nums:
t_value *= (value-1) * value ** (f_nums[value]-1)
return t_value
def solve(input_array):
output = []
for item in input_array:
p, q = item[0], item[1]
r = 2 * p + 1
r //= math.gcd(r, q % r)
t_value = euler_func(r)
for value in factor_finder(t_value):
while t_value % value == 0 and pow(2, t_value // value, r) == 1:
t_value //= value
output.append(2 * p - t_value)
return output
print(solve([[4, 2]])) 입력
[[4, 2]]
출력
[2]