CF 317D - Game with Powers

CF 317D - Game with Powers

Rating: 2300
Tags: dp, games
Solve time: 1m 58s
Verified: yes

Solution

Problem Understanding

We are asked to determine the winner of a two-player game involving numbers from 1 to n. The players, Vasya and Petya, take turns picking numbers. Once a number x is chosen, neither x nor any of its higher integer powers (_x_², _x_³, …) can be chosen in future turns. Vasya goes first. The player who cannot choose a number on their turn loses. The task is to print the winner if both play optimally.

The input is a single integer n up to 10^9, which immediately rules out any approach that tries to explicitly simulate all moves, because storing or iterating over 10^9 numbers is impractical. This suggests we need an approach that works on a structural property of the numbers rather than their individual identities.

Edge cases arise when n is very small. For instance, if n = 1, Vasya wins immediately by taking the only number. If n = 2, Vasya takes 1, Petya takes 2, and Vasya has no move, so Petya wins. Another subtle case is when n is a perfect power (like 16); the interplay of numbers and their powers must be carefully considered. A naive simulation would fail in these cases because it would not exploit the combinatorial structure of powers, leading to incorrect predictions of the winner.

Approaches

A brute-force approach is to model this game recursively or with dynamic programming on the set {1…n}, marking numbers as chosen and recursively computing which player wins from any given state. For each state, we would try all remaining numbers and remove their powers, then call recursively. This is correct in principle but infeasible for n = 10^9 because the state space is enormous and the recursion depth would be too large.

The key insight is to treat numbers as forming independent "power chains." For example, choosing 2 blocks 2, 4, 8, 16, … Choosing 3 blocks 3, 9, 27, … and so on. The game then decomposes into independent chains, each of which is a standard one-pile Nim game: if a chain has length l, its Grundy number is l mod 2 because each chain behaves like a single-pile take-away game where any number of stones can be taken at once. Thus, the winner is determined by computing the XOR of the Grundy numbers of all chains.

Chains correspond to numbers that are powers of some base, but we need to avoid double-counting. For instance, 8 is 2³ and also 8¹, but it belongs to the chain starting at 2. So, we only consider chains whose base is not a perfect power of a smaller integer. Numbers that are not part of any chain longer than 1 are themselves independent and count as chains of length 1.

Once we know the chain lengths, we compute the XOR (Nim-sum) of their Grundy numbers. If the XOR is zero, the second player wins; otherwise, the first player wins.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n log n) per recursion	O(n)	Too slow
Optimal	O(sqrt(n))	O(sqrt(n))	Accepted

Algorithm Walkthrough

1. Initialize an empty set to store numbers that have been assigned to chains. This prevents double-counting.
2. Iterate over possible bases b from 2 upwards. Stop when b² > n because higher powers would exceed n immediately.
3. For each base b, check if it has already been included in a previous chain (if b is a perfect power, skip it). This ensures each number appears in exactly one chain.
4. For each base b, compute the length of its chain: repeatedly multiply b by itself until the result exceeds n, counting the numbers. Mark all numbers in this chain as used.
5. Compute the XOR of the lengths of all chains modulo 2. Also include remaining numbers not in any chain (these are effectively chains of length 1) in the XOR.
6. If the final XOR is non-zero, Vasya (the first player) wins. Otherwise, Petya wins.

Why it works: the decomposition into chains ensures each number only interacts with others in its chain. The game then becomes a disjoint sum of independent single-pile Nim games, where the XOR of their Grundy numbers dictates the winner. Marking used numbers guarantees no double-counting. Chains of length 1 for remaining numbers account for all numbers not in a perfect-power chain.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    used = set()
    xor_sum = 0
    b = 2
    while b * b <= n:
        if b not in used:
            x = b
            count = 0
            while x <= n:
                used.add(x)
                count += 1
                x *= b
            xor_sum ^= count % 2
        b += 1
    remaining = n - len(used)
    xor_sum ^= remaining % 2
    print("Vasya" if xor_sum else "Petya")

solve()

The used set tracks numbers that are part of any power chain. The loop over b ensures we only start chains from numbers that are not themselves perfect powers, which prevents double-counting. We multiply repeatedly to form chains, counting their length for the XOR calculation. Remaining numbers not in any chain are treated as chains of length 1, and their contribution is XORed as well. Finally, the winner is determined by checking if the XOR sum is zero.

Worked Examples

Sample Input 1

Step	b	Chain	Count	XOR so far	Remaining
2	2	2,4,8,... ≤ n	1	1	n-1

Vasya wins because XOR ≠ 0.

Custom Input

10

Step	b	Chain	Count	XOR
2	2	2,4,8	3	1
3	3	3,9	2	1^0=1
4	skipped
remaining	1,5,6,7,10	5	1^1=0

Petya wins because XOR = 0.

These tables show that counting chain lengths modulo 2 and including remaining numbers correctly predicts the winner.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(sqrt(n) log n)	The outer loop runs up to √n, inner multiplication grows geometrically
Space	O(sqrt(n))	Only storing numbers in chains, max chain numbers ≈ √n

This is feasible for n ≤ 10^9 within 1 second.

Test Cases

import sys, io

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

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

# small n
assert run("2\n") == "Petya", "n=2"

# small n with powers
assert run("10\n") == "Petya", "n=10"

# large n
assert run("1000000000\n") in {"Vasya", "Petya"}, "n=1e9"

# n is perfect square
assert run("16\n") == "Vasya", "n=16"

# n is prime
assert run("7\n") == "Vasya", "n=7"

Test input	Expected output	What it validates
1	Vasya	minimum input, immediate win
2	Petya	small input, first move loses
10	Petya	mid-size input, multiple chains and leftovers
16	Vasya	perfect power input
7	Vasya	prime input, no chains beyond length 1

Edge Cases

For n = 1, the algorithm initializes used empty, no chains are formed, remaining = 1, XOR = 1, Vasya wins. For n = 2, base 2 forms a chain of length 1, remaining = 1, XOR = 1^1 = 0, Petya wins. For a large n, the same logic scales because chain generation grows geometrically, never exceeding n, and the XOR computation handles both chains and remaining numbers uniformly. The algorithm correctly separates perfect power chains from independent numbers, avoiding double-counting.