Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Flavius Josephus Reloaded
Description Flavius Josephus once was trapped in a cave together with his comrade soldiers surrounded by Romans. All of Josephus’ fellow soldiers preferred not to surrender but to commit suicide. So they all formed a circle and agreed on a number It is a lesser known fact that the souls of Josephus and his comrades were all born again in modern times. Obviously Josephus and his reborn fellow soldiers wanted to avoid a similar fiasco in the future. Thus they asked a consulting company to work out a better decision scheme. The company came up with the following scheme: - For the sake of tradition all soldiers should stand in a circle. This way a number between 0 and
*N*− 1 is assigned to each soldier, where*N*is the number of soldiers. - As changing numbers in the old scheme turned out to be horribly inefficient, the number assigned to a soldier will not change throughout the game.
- The consulting company will provide two numbers
*a*and*b*which will be used to calculate the number of the next soldier as follows: Let*x*be the number of the current soldier, then the number of the next soldier is the remainder of*a · x*^{2}+*b*mod*N*. - We start with the soldier with number 0 and each soldier calculates the number of the next soldier according to the formula above.
- As everyone deserves a second chance a soldier will commit suicide once his number is calculated for the second time.
- In the event that the number of a soldier is calculated for the third time the game will end and all remaining soldiers will surrender.
You are to write a program that given the number of soldiers Input The input file consists of several test cases. Each test case consists of a single line containing the three integers Output For each test case output a single line containing the number of soldiers that survive. Sample Input 2 1 1 5 1 1 10 3 7 101 9 2 698253463 1 181945480 1000000000 999999999 999999999 0 Sample Output 0 2 4 96 698177783 999999994 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator