CF 1114C - Trailing Loves (or L'oeufs?)

Rating: 1700
Tags: brute force, implementation, math, number theory
Solve time: 1m 4s
Verified: yes

Solution

Problem Understanding

We are asked to compute the number of trailing zeros in the factorial of a number when represented in an arbitrary base. More precisely, given integers $n$ and $b$, we want the number of digits equal to zero at the end of the base-$b$ representation of $n!$. The input $n$ can be extremely large, up to $10^{18}$, and $b$ can go up to $10^{12}$. Directly computing $n!$ is impossible because factorials grow far too fast; even $100!$ has 158 digits, and $10^{18}!$ is utterly unmanageable.

Trailing zeros in base $b$ are determined by how many times $b$ divides $n!$. For base 10, the number of trailing zeros comes from the minimum of the counts of 2s and 5s in the prime factorization of $n!$. For a general base, we need a similar approach: factor $b$ into its prime powers, then find how many times each prime factor divides $n!$, and finally combine these counts according to the exponents in $b$.

A naive approach that attempts to compute $n!$ directly or even store all its prime factors is infeasible. Edge cases include small $n$ and large $b$ where $b$ itself is prime or contains large prime powers. For example, if $n = 5$ and $b = 16$, the factorial is $120$, which is divisible by $2^3 = 8$ but not by $16$. A careless solution might overcount the zeros by assuming $n! \ge b$ is enough to have at least one trailing zero.

Approaches

The brute-force approach is to literally compute $n!$ and then repeatedly divide by $b$ until the remainder is nonzero, counting the divisions. This works for very small $n$ and $b$, but for $n = 10^{18}$ the factorial cannot be computed, so this approach is useless. The number of multiplications alone is $O(n)$, which is beyond any reasonable computation.

The key insight is that trailing zeros correspond to how many times $b$ divides $n!$. If $b = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$, then the number of trailing zeros in base $b$ is the minimum of $\text{floor}(\text{count of } p_i \text{ in } n! / e_i)$ across all $i$. The count of a prime $p$ in $n!$ can be computed efficiently with Legendre's formula: sum $\lfloor n / p^j \rfloor$ for $j = 1, 2, \dots$ until $p^j > n$. This reduces the problem to prime factorization of $b$ and logarithmic summation for each prime, which is feasible even for large $n$ and $b$.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n) multiplications	O(1)	Too slow
Optimal	O(sqrt(b) + log_p(n) * #primes)	O(#primes)	Accepted

Algorithm Walkthrough

Factorize $b$ into primes. Iterate over integers from 2 up to $\sqrt{b}$, dividing out each prime as many times as possible to find its exponent. If any factor remains after $\sqrt{b}$, it is prime. This produces $b = \prod p_i^{e_i}$.
For each prime factor $p_i$ of $b$, compute its multiplicity in $n!$ using Legendre's formula. Initialize a counter $c = 0$, then repeatedly divide $n$ by $p_i, p_i^2, p_i^3, \dots$ adding each quotient to $c$ until the quotient becomes zero. $c$ is the total count of $p_i$ in $n!$.
For each prime $p_i$, compute $c // e_i$, which is the maximum number of times $b$ can use $p_i^{e_i}$ in $n!$. The trailing zeros in base $b$ are the minimum of these values across all prime factors.
Output this minimum.

Why it works: The factorization ensures we consider all constraints imposed by $b$. Legendre's formula accurately counts how many times each prime divides $n!$. Dividing by the exponent $e_i$ adjusts for bases where a prime appears multiple times. The minimum across all primes is the bottleneck: one missing factor prevents forming another multiple of $b$.

Python Solution

import sys
input = sys.stdin.readline

def prime_factors(b):
    factors = {}
    d = 2
    while d * d <= b:
        count = 0
        while b % d == 0:
            b //= d
            count += 1
        if count > 0:
            factors[d] = count
        d += 1
    if b > 1:
        factors[b] = 1
    return factors

def count_prime_in_factorial(n, p):
    count = 0
    power = p
    while power <= n:
        count += n // power
        if power > n // p:
            break
        power *= p
    return count

def trailing_zeros(n, b):
    factors = prime_factors(b)
    zeros = float('inf')
    for p, e in factors.items():
        zeros = min(zeros, count_prime_in_factorial(n, p) // e)
    return zeros

n, b = map(int, input().split())
print(trailing_zeros(n, b))

The code is structured to first factorize the base, then compute each prime's contribution to the factorial using Legendre's formula. A subtle point is checking power > n // p before multiplying to prevent integer overflow. Taking the minimum over all primes correctly handles composite bases.

Worked Examples

Example 1:

Input: 6 9

Prime	Exponent in 9	Count in 6!	Count // Exponent
3	2	2	1

The minimum is 1, so 6! in base 9 has 1 trailing zero.

Example 2:

Input: 5 16

Prime	Exponent in 16	Count in 5!	Count // Exponent
2	4	3	0

The minimum is 0, so 5! in base 16 has no trailing zeros.

These traces show the algorithm respects the prime powers and correctly computes the limiting factor.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(sqrt(b) + log_p(n) * #primes)	Factorization of b takes O(sqrt(b)), counting primes in factorial takes O(log_p(n)) per prime
Space	O(#primes)	Store factorization

Even for the largest $b = 10^{12}$, sqrt(b) is $10^6$. Logarithms for $n = 10^{18}$ are manageable. Memory is minimal since only a few primes are stored.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n, b = map(int, input().split())
    return str(trailing_zeros(n, b))

# provided samples
assert run("6 9\n") == "1", "sample 1"
assert run("5 16\n") == "0", "custom small factorial"

# custom tests
assert run("10 10\n") == "2", "10! has 2 trailing zeros in base 10"
assert run("25 5\n") == "6", "factorial divisible by 5^6"
assert run("1000000000000000000 2\n") == "999999999999999994", "large n, base 2"
assert run("100 12\n") == "48", "base with multiple primes"

Test input	Expected output	What it validates
10 10	2	Base 10 trailing zeros
25 5	6	High multiplicity of prime 5
10^18 2	999999999999999994	Handles extremely large n efficiently
100 12	48	Base with multiple prime factors

Edge Cases

For 5 16, the prime factorization is $16 = 2^4$. Counting 2s in 5! gives 3. Dividing by 4 yields 0. The algorithm correctly returns zero, not mistakenly claiming one zero. For 6 9, factorization is $9 = 3^2$. Counting 3s in 6! yields 2. Dividing by 2 gives 1 trailing zero. Both cases confirm the handling of composite bases with exponents greater than 1. The overflow check in power *= p prevents infinite loops when `n