19593번 - 다도해 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 256 MB | 152 | 74 | 44 | 38.596% |
문제
당신은 N개의 작은 섬으로 이루어진 다도해에 다리를 건설하여 임의의 한 섬에서 임의의 다른 섬으로 도달 가능하게 하고 싶다. 현재는 아무 다리도 없는 상태이다.
섬은 0번 부터 N-1번까지 번호가 붙어있다.
당신은 아래와 같은 알고리즘에 따라 다리를 건설하기로 했다.
- 세 개의 양의 정수 Seed, A, B 를 고른다. 이후, E[ i ], X[ i ], Y[ i ] 를 아래와 같이 정의한다.
- E[ 1 ] = Seed % N2 그리고 E[ i ] = (E[ i-1 ] * A + B) % N2 (i > 1). (각각의 E[i] 값은 어느 두 섬을 연결하는 다리를 지을지 결정한다.)
- X[ i ] = E[ i ] / N 그리고 Y[ i ] = E[ i ] % N (i ≥ 1).
- 위 두 수식에서 "%" 는 정수 나머지 연산을 나타내는 Modulo 이며, "/"은 정수 나눗셈 연산이다.
- 오늘부터 1일 후 (즉, 내일) X[ 1 ] 번 섬과 Y[ 1 ]번 섬을 연결하는 다리를 건설한다. 만약 X[ 1 ] = Y[ 1 ]이면 이 날은 건설은 하지 않고 논다.
- 오늘 부터 i일 후, X[ i ] 번 섬과 Y[ i ] 번 섬을 연결하는 다리를 건설한다. 만약 X[ i ] = Y[ i ] 이거나 이미 두 섬을 잇는 다리가 있다면, 이 날은 건설은 하지 않고 논다.
위 알고리즘에 따라 다리를 건설 할 때, 당신은 오늘 부터 몇 일이 지난 후 (M일 후) 목적을 달성할지 궁금하다.
예를 들어 N = 4, Seed = 2020, A = 2, B = 3 인 경우를 생각해보자.
- E[ 1 ] = 2020 % 16 = 4, X[ 1 ] = 4 / 4 = 1, Y[ 1 ] = 4 % 4 = 0. 따라서 (1번섬, 0번섬) 을 잇는 다리를 건설한다.
- E[ 2 ] = (4 * 2 + 3) % 16 = 11, X[ 2 ] = 11 / 4 = 2, Y[ 2 ] = 11 % 4 = 3. 따라서 (2번섬, 3번섬)을 잇는 다리를 건설한다.
- E[ 3 ] = (11 * 2 + 3) % 16 = 9, X[ 3 ] = 9 / 4 = 2, Y[ 3 ] = 9 % 4 = 1. 따라서 (2번섬, 1번섬)을 잇는 다리를 건설한다.
- 세 번째 다리를 건설한 후 임의의 한 섬에서 다른 섬으로 도달할 수 있으므로 이 때 M = 3이다.
다른 예로, N = 4, Seed = 2020, A = 3, B = 4 인 경우를 생각해보자.
- E[ 1 ] = 2020 % 16 = 4, X[ 1 ] = 4 / 4 = 1, Y[ 1 ] = 4 % 4 = 0. 따라서 (1번섬, 0번섬) 을 잇는 다리를 건설한다.
- E[ 2 ] = (4 * 3 + 4) % 16 = 0, X[ 2 ] = 0 / 4 = 0, Y[ 2 ] = 0 % 4 = 0. X,Y 값이 같으므로 다리를 건설하지 않는다.
- E[ 3 ] = (0 * 3 + 4) % 16 = 4, X[ 3 ] = 4 / 4 = 1, Y[ 3 ] = 4 % 4 = 0. 이미 다리가 있으므로 다리를 건설하지 않는다.
- 이 경우, (1번섬, 0번섬)을 잇는 다리 이외에 다른 다리를 건설하지 못한다. 따라서 이 때 위 조건을 만족하는 M은 존재하지 않는다.
입력으로 N, Seed, A, B가 주어졌을 때, 위 조건을 만족하는 M값을 구하여 출력한다. 만약 조건을 만족하는 M값이 없다면 0을 출력한다.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 네 개의 정수가 공백으로 구분되어 주어지는데, 순서대로 N, Seed, A, B 이다.
출력
조건을 만족하는 M이 존재하면 그 중 최소값을 출력하고, 존재하지 않으면 0을 출력한다.
제한
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 1,000
- 1 ≤ Seed, A, B ≤ 1,000,000,000
예제 입력 1
4 4 2020 2 3 4 2020 3 4 4 2020 9 7 5 2020 4 7
예제 출력 1
3 0 6 5
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호