CF 150A - Win or Freeze

We start with a number q written on paper. On each turn, a player must replace the current number with one of its non-trivial divisors, meaning a divisor strictly between 1 and the number itself. If a player cannot make a move, that player wins immediately.

codeforcescompetitive-programminggamesmathnumber-theory

CF 150A - Win or Freeze

Rating: 1400
Tags: games, math, number theory
Solve time: 2m 2s
Verified: no

Solution

Problem Understanding

We start with a number q written on paper. On each turn, a player must replace the current number with one of its non-trivial divisors, meaning a divisor strictly between 1 and the number itself.

If a player cannot make a move, that player wins immediately. This is the opposite of the usual normal-play game convention, where the player unable to move loses.

The task is to determine whether the first or second player wins when both play optimally. If the first player has a winning strategy, we also need to print one valid first move.

The input size is small in count, there is only one integer, but the value itself can be as large as 10^13. That rules out anything that tries to enumerate all divisors repeatedly or perform expensive recursive game-state exploration. A square root factorization up to roughly 3 * 10^6 is completely acceptable within 2 seconds, since sqrt(10^13) is about 3.16 * 10^6.

The tricky part is not performance, it is understanding the game logic correctly because of the unusual winning condition.

A very common mistake is to assume that "no moves means losing". That produces the exact opposite answer on many cases.

Consider:

Input:

2

The number 2 has no non-trivial divisors. The first player cannot move, so the first player wins immediately. The correct output is:

1
0

A careless implementation using standard Sprague-Grundy intuition would incorrectly print player 2.

Another subtle case is when the number is the product of exactly two primes.

Input:

6

The only legal moves are 2 and 3. Both are prime numbers, so the next player has no move and wins immediately. That means moving to 2 or 3 loses for the current player. Every possible move from 6 is bad, so 6 itself is losing.

The correct output is:

2

A naive recursive solution without carefully reversing the terminal condition often gets this backwards.

There is also a structural edge case around prime powers.

Input:

8

The legal moves are 2 and 4.

If we move to 2, the opponent cannot move and wins immediately, so that move is losing.

If we move to 4, the opponent must move to 2, and then we cannot move and win.

So 8 is winning, and one valid first move is 4.

This case shows that the game is not determined only by whether the current number is composite. The factorization structure matters.

Approaches

A brute-force solution would treat every reachable number as a game state and recursively determine whether it is winning or losing. For a number x, we would enumerate all non-trivial divisors and recursively analyze them.

The recursion itself is manageable because every move strictly decreases the number, but the expensive part is divisor enumeration. In the worst case we would scan up to sqrt(x) for many states repeatedly. With x as large as 10^13, that quickly becomes wasteful.

The deeper issue is that we do not actually need full game search. The game has a very rigid structure because every move replaces the number with a proper divisor.

Let us classify states carefully.

A prime number has no legal moves. Since the player unable to move wins, every prime is a winning state.

Now look at a number with exactly one possible move, such as p^2.

Example:

9 -> 3

The move goes to a prime, which is winning for the next player. So 9 is losing.

Now look at p^3.

Example:

27 -> 9` or `3

Moving directly to 3 is bad because the opponent immediately wins. But moving to 9 is good because 9 is losing. So 27 is winning.

This alternating behavior continues for pure prime powers.

For numbers with at least two distinct prime factors, the situation becomes much simpler. We can almost always move to a losing state immediately.

The key observation is that the only losing states are numbers with an even total number of prime factors counted with multiplicity.

Let:

n = p1 * p2 * ... * pk

where repeated primes are counted repeatedly. Define:

Ω(n) = total count of prime factors with multiplicity

Examples:

Ω(12) = Ω(2^2 * 3) = 3
Ω(18) = Ω(2 * 3^2) = 3
Ω(36) = Ω(2^2 * 3^2) = 4

Every move removes at least one prime factor, so each move strictly decreases Ω(n).

A prime has Ω = 1 and is winning.

A number with Ω = 2 is losing because every move reaches a prime.

A number with Ω = 3 is winning because we can move to a state with Ω = 2.

By induction:

  • odd Ω(n) means winning
  • even Ω(n) means losing

The entire problem reduces to factoring the number and counting prime multiplicities.

If the count is even, player 2 wins.

If the count is odd:

  • if there is no legal move at all, print 0
  • otherwise print any divisor that leaves an even factor count

The easiest way is to divide by one prime factor.

Approach Time Complexity Space Complexity Verdict
Brute Force Exponential in number of reachable states O(depth) Too slow
Optimal O(sqrt(q)) O(1) Accepted

Algorithm Walkthrough

  1. Factorize the number q using trial division up to sqrt(q).

For every divisor d, repeatedly divide q by d while possible and count how many prime factors were removed. 2. If after trial division the remaining value is greater than 1, it is a prime factor larger than sqrt(original q), so increment the factor count once more. 3. Let cnt be the total number of prime factors counted with multiplicity.

Examples:

12 = 2 * 2 * 3 -> cnt = 3
18 = 2 * 3 * 3 -> cnt = 3
36 = 2 * 2 * 3 * 3 -> cnt = 4
  1. If cnt is even, print:
2

The current state is losing for the first player. 5. Otherwise the first player wins.

Print:

1
  1. Find any non-trivial divisor that leaves an even number of prime factors.

Dividing by one prime factor always reduces the count by exactly one, changing parity from odd to even. 7. If the original number is prime, there is no legal move. Print:

0
  1. Otherwise print:
q / p

where p is any prime factor of q.

Why it works

The invariant is the parity of the total number of prime factors.

Every move replaces n with a proper divisor. That means at least one prime factor disappears, so the value of Ω(n) strictly decreases.

A move changes the parity of Ω(n) because removing any positive number of prime factors flips parity if and only if that count is odd. Since we can always remove exactly one prime factor by dividing by a prime divisor, every odd state has a move to an even state.

Prime numbers have Ω = 1 and are winning because the current player cannot move.

Using induction on Ω(n):

  • all odd counts are winning
  • all even counts are losing

So parity completely determines the game outcome.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    original = n

    cnt = 0
    first_prime = -1

    d = 2
    while d * d <= n:
        while n % d == 0:
            if first_prime == -1:
                first_prime = d
            cnt += 1
            n //= d

        if d == 2:
            d = 3
        else:
            d += 2

    if n > 1:
        if first_prime == -1:
            first_prime = n
        cnt += 1

    if cnt % 2 == 0:
        print(2)
    else:
        print(1)

        if cnt == 1:
            print(0)
        else:
            print(original // first_prime)

solve()

The first part performs prime factorization using trial division. We repeatedly divide by each factor instead of removing it once because the game depends on multiplicity. For example, 12 = 2^2 * 3 must contribute 3 total factors, not 2.

The variable first_prime stores one prime divisor of the original number. Later, if the position is winning, dividing by this prime reduces the factor count by exactly one and flips parity.

The loop skips even numbers after checking 2, which slightly improves performance. Since sqrt(10^13) is only around 3 * 10^6, this implementation easily fits the time limit.

The condition cnt == 1 identifies primes. A prime has no legal non-trivial divisor, so even though the first player wins immediately, the required move output is 0.

A common implementation bug is forgetting to handle the remaining prime factor after the loop. For example, when factoring 10, after dividing by 2 we are left with 5. Since 5 * 5 > 5, the loop stops, and we must manually count that final prime.

Worked Examples

Example 1

Input:

6

Prime factorization:

6 = 2 * 3
Step Current n Factor found cnt
Start 6 - 0
Divide by 2 3 2 1
Remaining prime 1 3 2

cnt = 2, which is even.

Output:

2

This demonstrates the core losing configuration. Every move from 6 reaches a prime, and primes are winning states.

Example 2

Input:

8

Prime factorization:

8 = 2 * 2 * 2
Step Current n Factor found cnt
Start 8 - 0
Divide by 2 4 2 1
Divide by 2 2 2 2
Divide by 2 1 2 3

cnt = 3, which is odd.

We store first_prime = 2.

Winning move:

8 / 2 = 4

Output:

1
4

This example shows how moving to an even-factor-count state guarantees victory.

Complexity Analysis

Measure Complexity Explanation
Time O(sqrt(q)) Trial division checks divisors up to sqrt(q)
Space O(1) Only a few variables are stored

The maximum input is 10^13, so the largest square root we ever scan is roughly 3.16 * 10^6. That is easily fast enough in Python within a 2 second limit, especially with the optimization of skipping even numbers after 2.

Test Cases

# helper: run solution on input string, return output string
import sys, io

def solve():
    input = sys.stdin.readline

    n = int(input())
    original = n

    cnt = 0
    first_prime = -1

    d = 2
    while d * d <= n:
        while n % d == 0:
            if first_prime == -1:
                first_prime = d
            cnt += 1
            n //= d

        if d == 2:
            d = 3
        else:
            d += 2

    if n > 1:
        if first_prime == -1:
            first_prime = n
        cnt += 1

    out = []

    if cnt % 2 == 0:
        out.append("2")
    else:
        out.append("1")

        if cnt == 1:
            out.append("0")
        else:
            out.append(str(original // first_prime))

    return "\n".join(out)

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    return solve()

# provided sample
assert run("6\n") == "2", "sample 1"

# prime number
assert run("2\n") == "1\n0", "prime case"

# odd multiplicity
assert run("8\n") == "1\n4", "prime power"

# even multiplicity
assert run("36\n") == "2", "even factor count"

# large prime
assert run("9999999967\n") == "1\n0", "large prime"
Test input Expected output What it validates
2 1 0 Prime numbers are immediate wins
8 1 4 Odd factor count is winning
36 2 Even factor count is losing
9999999967 1 0 Large prime factorization edge case

Edge Cases

A prime number is the most counterintuitive case because the player with no moves wins.

Input:

2

Factorization:

2 = 2

So:

cnt = 1

Odd parity means the first player wins. Since there are no non-trivial divisors, the correct move output is:

0

The algorithm handles this through the special case cnt == 1.

Now consider a semiprime.

Input:

15

Factorization:

15 = 3 * 5

So:

cnt = 2

Even parity means losing.

Possible moves:

15 -> 3
15 -> 5

Both targets are prime, and primes are winning states because the next player cannot move. The algorithm correctly prints:

2

Now consider a higher prime power.

Input:

32

Factorization:

32 = 2^5

So:

cnt = 5

Odd parity means winning.

The algorithm chooses:

32 / 2 = 16

Now:

16 = 2^4

which has even parity and is losing.

Output:

1
16

This confirms that removing exactly one prime factor always flips the game state parity correctly.