### dumb_fish's blog

By dumb_fish, history, 6 weeks ago,

Problem Statement Two players are playing a game. They have A bundles of pencils of size B each.

They also have a number C that they chose randomly. They move in turns and the person who's unable to make a move loses.

For each move a person chooses a bundle and divides it into some number (more than one) of equal parts/bundles, the size of each one is expressed by an integer and is no less than C.

Each resulting part is also a bundle which can be divided in future by any player.

Find the winner of the game.

Problem Constraints 1 <= A <= 105

1 <= B, C <= 109

Input Format First argument is the integer A.

Second argument is the integer B.

Third argument is the integer C.

Output Format Return 1 of the First player wins, 0 if Second player wins.

Example Input Input 1:

A = 4 B = 8 C = 6 Input 2:

A = 1 B = 9 C = 2

Example Output Output 1:

0 Output 2:

1

Example Explanation Explanation 1:

Player 1 cannot divide any of the bundle, so that the divided bundles have size not less than 6. Hence he loses. Explanation 2:

They have only 1 bundle to start with. Player 1 has only one valid move where he divides this bundle into 3 bundles of size 3. After this Player 2 cannot divide bundles of size 3 further. Hence Player 2 loses.

Intuition

if A is even, player2 wins because player2 can mimic player1's move. But what if A is odd?

• -15

 » 6 weeks ago, # |   0 It's a Nim game: https://codeforces.com/blog/entry/66040
•  » » 6 weeks ago, # ^ |   0 But the operation is different than Nim Game. So how would it be solved for a game with odd number of piles?
•  » » » 6 weeks ago, # ^ |   0 Read the post I linked to. It can be generalized.
 » 6 weeks ago, # |   0 Are you referring to this problem? https://codeforces.com/problemset/problem/78/CThat player 2 always wins if $A$ is even is a great first step! In fact, you're almost done. The case for when $A$ is odd is not too far from that, and I suggest you think about it some more before looking at the problem's editorial.