백준19496 Guess by Remainder

작성일 | In

문제 링크

  • http://icpc.me/19496

풀이

$N = 1$일 때는 항상 정답이 1이므로 0번의 질의로 정답을 알 수 있습니다.
그렇지 않은 경우, $\text{lcm}(1, 2, \cdots, N) - 1$에 대한 결과 +1이 문제의 정답이 됩니다. 큰 수 곱셈을 구현하는 것은 매우 귀찮기 때문에 파이썬을 사용하는 것이 좋습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
N = int(input())
isP = [1]*(N+1)

isP[0] = isP[1] = 0
prime = []
for i in range(2, N+1):
	if isP[i] == 1:
		prime.append(i)
	j = i * i
	while j <= N:
		isP[j] = 0
		j += i

res = 1
for i in prime:
	pw = 1
	j = i
	while j <= N:
		pw *= i
		j *= i
	res *= pw

if N == 1:
    print("! 1")
else:
    print('?', res - 1)
    print('!', int(input()) + 1)