Thursday, August 14, 2014

National Olympiad in Informatics, China, 2012 Day 1, Problem 1 - Random Number Generator

Problem Link

A(n) = (a*A(n-1)+c) mod m 이고 A(0)가 주어졌을 때, A(n) mod g를 구하는 문제.

g가 10^8 이하이고, 나머지 값들은 모두 10^18 이하라서, 계산 도중 long long 범위를 넘어갈 수 있음에 주의해야한다. log 시간복잡도에 a^x 계산과 1+a+a^2+....a^x 계산을 할 줄 알면 풀 수 있다. 그리고 ( X mod m ) mod g를 계산할 때에는 X나 m을 g로 나눈 나머지로 계산하면 안되고, m으로 나눈 나머지로 다 계산한 다음에 g로 나눈 나머지를 계산해야한다. modular를 공부했었다면 다 아는 사실이겠지만...

No comments:

Post a Comment