시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 138 18 15 50.000%

문제

홍준이는 통계학을 공부하다가 ‘무작위 추출’의 매력에 푹 빠졌고, 난수 발생기를 이용해 직접 ‘무작위 추출’을 한다. 홍준이는 일차 점화식으로 생성되는 수열을 이용한 난수 발생기가 적당하다고 생각했다. 수열을 만들기 위해서는 음이 아닌 정수 m, a, c, X0이 필요하다. 수열 <Xn>의 점화식은 다음과 같다:

Xn+1 = (aXn + c) mod m

"A mod m"이라는 말은 A를 m으로 나눈 나머지를 뜻한다.

최종적으로, Xn을 양의 정수 g로 나눈 나머지가 난수로 사용한다. 따라서 생성된 난수는 0, 1, …, g-1사이의 값을 가지게 될 것이다.

착한 명우는, 친구 홍준이의 속마음을 읽고, 난수 발생기를 만들어주려고 한다. 명우를 도와 홍준이에게 줄 난수 발생기 프로그램을 작성하시오.

입력

첫째 줄에 6개의 정수 m, a, c, X0, n, g (m, a, c, X0, n ≤ 1018, g ≤ 108)가 차례대로 주어진다. a, c, X0는 음이 아닌 정수이고 m, n, g는 양의 정수이다.

출력

첫째 줄에 Xn mod g의 값을 출력한다.

예제 입력 1

11 8 7 1 5 3

예제 출력 1

2

힌트

예제 입력으로 생성되는 수열 <Xn>을 구해보면 아래와 같다.

k 0 1 2 3 4 5
Xk 1 4 6 0 7 8

따라서 답은 X5 mod g = 8 mod 3 = 2이다.

W3sicHJvYmxlbV9pZCI6IjExNjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJSYW5kb20gTnVtYmVyIEdlbmVyYXRvciIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNjRkXHVjOTAwXHVjNzc0XHViMjk0IFx1ZDFiNVx1YWNjNFx1ZDU1OVx1Yzc0NCBcdWFjZjVcdWJkODBcdWQ1NThcdWIyZTRcdWFjMDAgJmxzcXVvO1x1YmIzNFx1Yzc5MVx1YzcwNCBcdWNkOTRcdWNkOWMmcnNxdW87XHVjNzU4IFx1YjllNFx1YjgyNVx1YzVkMCBcdWQ0NzkgXHViZTYwXHVjODRjXHVhY2UwLCBcdWIwOWNcdWMyMTggXHViYzFjXHVjMGRkXHVhZTMwXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWM5YzFcdWM4MTEgJmxzcXVvO1x1YmIzNFx1Yzc5MVx1YzcwNCBcdWNkOTRcdWNkOWMmcnNxdW87XHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHVkNjRkXHVjOTAwXHVjNzc0XHViMjk0IFx1Yzc3Y1x1Y2MyOCBcdWM4MTBcdWQ2NTRcdWMyZGRcdWM3M2NcdWI4NWMgXHVjMGRkXHVjMTMxXHViNDE4XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NWMgXHViMDljXHVjMjE4IFx1YmMxY1x1YzBkZFx1YWUzMFx1YWMwMCBcdWM4MDFcdWIyZjlcdWQ1NThcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTg4XHViMmU0LiBcdWMyMThcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOCBtLCBhLCBjLCBYPHN1Yj4wPFwvc3ViPlx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuIFx1YzIxOFx1YzVmNCAmbHQ7WDxzdWI+bjxcL3N1Yj4mZ3Q7XHVjNzU4IFx1YzgxMFx1ZDY1NFx1YzJkZFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0OjxcL3A+XHJcblxyXG48cD5YPHN1Yj5uKzE8XC9zdWI+ID0gKGFYPHN1Yj5uPFwvc3ViPiArIGMpIG1vZCBtPFwvcD5cclxuXHJcbjxwPiZxdW90O0EgbW9kIG0mcXVvdDtcdWM3NzRcdWI3N2NcdWIyOTQgXHViOWQwXHVjNzQwIEFcdWI5N2MgbVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHVjODg1XHVjODAxXHVjNzNjXHViODVjLCBYPHN1Yj5uPFwvc3ViPlx1Yzc0NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IGdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1YWMwMCBcdWIwOWNcdWMyMThcdWI4NWMgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjMGRkXHVjMTMxXHViNDFjIFx1YjA5Y1x1YzIxOFx1YjI5NCAwLCAxLCAmaGVsbGlwOywgZy0xXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjOGMgXHViNDIwIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzI5XHVkNTVjIFx1YmE4NVx1YzZiMFx1YjI5NCwgXHVjZTVjXHVhZDZjIFx1ZDY0ZFx1YzkwMFx1Yzc3NFx1Yzc1OCBcdWMxOGRcdWI5YzhcdWM3NGNcdWM3NDQgXHVjNzdkXHVhY2UwLCBcdWIwOWNcdWMyMTggXHViYzFjXHVjMGRkXHVhZTMwXHViOTdjIFx1YjljY1x1YjRlNFx1YzViNFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmE4NVx1YzZiMFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVkNjRkXHVjOTAwXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzkwNCBcdWIwOWNcdWMyMTggXHViYzFjXHVjMGRkXHVhZTMwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDZcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IG0sIGEsIGMsIFg8c3ViPjA8XC9zdWI+LCBuLCBnIChtLCBhLCBjLCBYPHN1Yj4wPFwvc3ViPiwgbiAmbGU7IDEwPHN1cD4xODxcL3N1cD4sIGcgJmxlOyAxMDxzdXA+ODxcL3N1cD4pXHVhYzAwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGEsIGMsIFg8c3ViPjA8XC9zdWI+XHViMjk0IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzc0XHVhY2UwIG0sIG4sIGdcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFg8c3ViPm48XC9zdWI+IG1vZCBnXHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjMGRkXHVjMTMxXHViNDE4XHViMjk0IFx1YzIxOFx1YzVmNCAmbHQ7WDxzdWI+bjxcL3N1Yj4mZ3Q7XHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1YmE3NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MzUlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+azxcL3RoPlxyXG5cdFx0XHQ8dGg+MDxcL3RoPlxyXG5cdFx0XHQ8dGg+MTxcL3RoPlxyXG5cdFx0XHQ8dGg+MjxcL3RoPlxyXG5cdFx0XHQ8dGg+MzxcL3RoPlxyXG5cdFx0XHQ8dGg+NDxcL3RoPlxyXG5cdFx0XHQ8dGg+NTxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+WDxzdWI+azxcL3N1Yj48XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjQ8XC90ZD5cclxuXHRcdFx0PHRkPjY8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjg8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1YjUzMFx1Yjc3Y1x1YzExYyBcdWIyZjVcdWM3NDAgWDxzdWI+NTxcL3N1Yj4gbW9kIGcgPSA4IG1vZCAzID0gMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExNjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiIiLCJkZXNjcmlwdGlvbiI6IjxwPkRvbmdEb25nIHJlY2VudGx5IGJlY2FtZSBvYnNlc3NlZCB3aXRoIHJhbmRvbWl6YXRpb24sIGFuZCByYW5kb20gbnVtYmVyIGdlbmVyYXRvcnMgaXMgdGhlIGZvdW5kYXRpb24gb2YgcmFuZG9taXphdGlvbi4gRG9uZ0RvbmcgcGxhbnMgdG8gdXNlIHRoZSBsaW5lYXIgY29uZ3J1ZW50aWFsIG1ldGhvZCB0byBnZW5lcmF0ZSBhIG51bWJlciBzZXF1ZW5jZS4gVGhpcyBtZXRob2QgcmVxdWlyZXMgZm9yIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIHBhcmFtZXRlcnMgbSwgYSwgYywgWDxzdWI+MDxcL3N1Yj4uIFRoZW4sIGEgcmFuZG9tIHNlcXVlbmNlICZsdDtYPHN1Yj5uPFwvc3ViPiZndDsgY2FuIGJlIGdlbmVyYXRlZCB1c2luZyB0aGUgZm9sbG93aW5nIGZvcm11bGE6PFwvcD5cclxuXHJcbjxwPlg8c3ViPm4rMTxcL3N1Yj4gPSAoYVg8c3ViPm48XC9zdWI+ICsgYykgbW9kIG08XC9wPlxyXG5cclxuPHA+d2hlcmUgJnF1b3Q7bW9kIG0mcXVvdDsgbWVhbnMgdG8gdGFrZSB0aGUgcmVtYWluZGVyIGFmdGVyIHRoZSBsZWZ0IGhhbmQgZXhwcmVzc2lvbiBoYXMgZGl2aWRlZCBtLiBJdCBjYW4gYmUgb2JzZXJ2ZWQgZnJvbSB0aGlzIGVxdWF0aW9uIHRoYXQgdGhlIG5leHQgbnVtYmVyIGluIGEgc2VxdWVuY2Ugd2lsbCBhbHdheXMgYmUgYmFzZWQgb2ZmIG9mIHRoZSBjdXJyZW50IG51bWJlci48XC9wPlxyXG5cclxuPHA+U2VxdWVuY2VzIGdlbmVyYXRlZCB0aGlzIHdheSBhcmUgdmVyeSByYW5kb20gaW4gbmF0dXJlLCB3aGljaCBpcyB3aHkgdGhpcyBtZXRob2QgaGFzIGJlZW4gdXNlZCBleHRlbnNpdmVseS4gRXZlbiByYW5kb21pemF0aW9uIGZ1bmN0aW9ucyBpbiB0aGUgd2lkZWx5IHVzZWQgc3RhbmRhcmQgbGlicmFyaWVzIG9mIEMrKyBhbmQgUGFzY2FsIGVtcGxveSB0aGlzIG1ldGhvZC48XC9wPlxyXG5cclxuPHA+RG9uZ0Rvbmcga25vd3MgdGhhdCBzZXF1ZW5jZXMgcHJvZHVjZWQgdGhpcyB3YXkgYXJlIHZlcnkgcmFuZG9tLCBidXQgaGUgaXMgYWxzbyBpbXBhdGllbnQgYWJvdXQgd2FudGluZyB0byBrbm93IHRoZSB2YWx1ZSBYPHN1Yj5uPFwvc3ViPiBhcyBzb29uIGFzIHBvc3NpYmxlLiBTaW5jZSBEb25nRG9uZyBuZWVkcyBhIHJhbmRvbSBudW1iZXIgdGhhdCYjMzk7cyBvbmUgb2YgMCwgMSwgJmhlbGxpcDssIGctMSwgaGUgd2lsbCBoYXZlIHRvIG1vZHVsbyB0aGUgbnVtYmVyIFg8c3ViPm48XC9zdWI+IGJ5IGcgdG8gZ2V0IHRoZSBmaW5hbCByZXN1bHQuIEFsbCB5b3UgaGF2ZSB0byBkbyBpcyBkZXRlcm1pbmUgdGhlIHZhbHVlIG9mIFg8c3ViPm48XC9zdWI+IG1vZCBnIGZvciBEb25nRG9uZy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiA2IHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBtLCBhLCBjLCBYPHN1Yj4wPFwvc3ViPi4gbiwgYW5kIGcgKG0sIGEsIGMsIFg8c3ViPjA8XC9zdWI+LCBuICZsZTsgMTA8c3VwPjE4PFwvc3VwPiwgZyAmbGU7IDEwPHN1cD44PFwvc3VwPikuIEhlcmUsIGEsIGMsIGFuZCBYPHN1Yj4wPFwvc3ViPiBhcmUgbm9uLW5lZ2F0aXZlIHdoaWxlIG0sIG4sIGcgYXJlIHBvc2l0aXZlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyLCB0aGUgdmFsdWUgb2YgWDxzdWI+bjxcL3N1Yj4gbW9kIGcuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBmaXJzdCBmZXcgdGVybXMgb2YgJmx0O1g8c3ViPm48XC9zdWI+Jmd0OyBhcmU6PFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDozNSVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5rPFwvdGg+XHJcblx0XHRcdDx0aD4wPFwvdGg+XHJcblx0XHRcdDx0aD4xPFwvdGg+XHJcblx0XHRcdDx0aD4yPFwvdGg+XHJcblx0XHRcdDx0aD4zPFwvdGg+XHJcblx0XHRcdDx0aD40PFwvdGg+XHJcblx0XHRcdDx0aD41PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5YPHN1Yj5rPFwvc3ViPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+ODxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+VGh1cyB0aGUgYW5zd2VyIGlzIFg8c3ViPjU8XC9zdWI+IG1vZCBnID0gOCBtb2QgMyA9IDIuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > National Olympiad in Informatics (China) > NOI 2012 1번

  • 문제를 번역한 사람: appa