2925번 - 신기한 물체 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 | 128 MB | 122 | 26 | 21 | 32.308% |
문제
어느 날, 상근이는 길을 걷던 중에 신기한 물체를 발견했다. 외계의 것으로 추정되는 이 물체의 왼편에는 빈 박스가 N개 있었다. 기계의 사용방법을 알아내기 위해서 하루종일 기계를 더듬거렸고, 마침내 상근이는 이 기계를 어떻게 사용하는지를 알게되었다.
기계는 정수 4개 L, R, A, B를 입력으로 받는다. 크고 빨갛게 빛나는 실행버튼을 누르면 기계는 다음과 같은 움직인다.
먼저, L번 박스에 들어 있는 돌의 개수를 A mod B개로 만든다. 그 다음 L+1번 박스에 들어 있는 돌을 (2*A) mod B개로 만든다. 마찬가지로, L+2번 박스에 들어 있는 돌을 (3*A ) mod B개로 만든다. 즉, L번과 R번 사이의 X번 박스에 들어 있는 돌의 개수를 ((X-L+1)*A) mod B개로 만드는 것이다. R번 박스까지 돌을 채우고나면, 기계는 다음 명령을 기다린다.
기계에 여러 가지 명령을 내리던 중에, 상근이는 어떤 박스의 구간에 들어있는 돌의 개수가 궁금해졌다.
상근이가 기계에 입력한 명령이 주어졌을 때, 이 기계를 시뮬레이팅 하면서, 상근이의 궁금증도 해결해주는 프로그램을 작성하시오.
입력
첫째 줄에 박스의 수 N과 쿼리의 수 Q가 주어진다. (1 ≤ N ≤ 1,000,000,000, 1 ≤ Q ≤ 50,000)
다음 Q개 줄에는 시뮬레이션에 관한 정보가 주어진다.
만약, 정보가 1로 시작한다면, 형식은 "1 L R A B" (1 ≤ L ≤ R ≤ N, 1 ≤ A, B ≤ 1,000,000)가 된다. 이 뜻은 상근이가 기계에 L, R, A, B를 입력했다는 뜻이다.
정보가 2로 시작한다면, 형식은 "2 L R"이 된다. (1 ≤ L ≤ R ≤ N) 이 뜻은 상근이가 L과 R번 박스 사이에 들어있는 돌의 개수를 궁금했다는 뜻이고, 개수를 구한뒤, 출력해야 한다. L과 R도 범위에 포함된다.
출력
2로 시작하는 명령이 들어올 때 마다, 그 구간에 들어있는 돌의 개수를 출력한다.
예제 입력 1
6 3 2 1 6 1 1 5 1 2 2 1 6
예제 출력 1
0 3
예제 입력 2
4 5 1 1 4 3 4 2 1 1 2 2 2 2 3 3 2 4 4
예제 출력 2
3 2 1 0
예제 입력 3
4 4 1 1 4 7 9 2 1 4 1 1 4 1 1 2 1 4
예제 출력 3
16 0
출처
Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #1 6번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호