Gems in the maze
시간 제한3초메모리 제한2048 MB
n개의 방이 각각 보석 하나를 품고 있고, 방마다 f(v) = (a*v^2 + b*v + c) mod n으로 가는 터널과 미로 밖으로 나가는 터널이 하나씩 있다. 나가기 전까지 지날 수 있는 서로 다른 방의 최대 개수를 구한다.
문제
Scrooge McDuck has a new plan how to increase his wealth. He found ancient ruins with an extraordinary maze. This maze consists of n chambers. The chambers are numbered 0 through n − 1. Each chamber contains exactly one gem. Chambers are connected by one-way tunnels. Each chamber has exactly two outgoing tunnels: one leads to the chamber with number (a ⋅ v2 + b ⋅ v + c) modn, the other will bring you out of the maze.
You can enter the maze at any location, move along the tunnels and collect the gems. But once you leave the maze, you’ll trigger a self-destruct mechanism – the ceiling of the maze will collapse and all the gems that you did not collect will be lost forever.
Scrooge wants to know the maximum number of gems he can take from the maze.
입력
The first line of the input file contains four integers a, b, c, and n – the numbers that describe one particular maze.
출력
Output a single line containing a single integer – the maximum number of gems that can be taken from the maze.
힌트
The starting chamber matters. For instance, assume that in the first example test case Scrooge starts in the chamber 0. His only two options are a tunnel that leads back to chamber 0 and a tunnel that leads outside – not much of a choice. A much better strategy is to start in the chamber 2 and follow the path 2 → 8 → 16 → 32 → 0 → outside.