UVa 10139

Summary

Summary of the problem statement goes here.

Explanation

1. Any number, $x$ , can be represented as product of powers of primes: $x=p_{1}^{a_{1}}*p_{2}^{a_{2}}*p_{3}^{a_{3}}\ldots p_{m}^{a_{m}}\ldots$ . This is called the "prime factorization" of $x$ .
2. $b|a\iff a=kb$ To solve this problem, find the prime factorization of the number to divide the factorial and see if the powers of its prime factorization are less than or equal to the powers of those same prime factors in the factorial. The power of a prime factor, $p$ , in $n!$ can be found using:

For example, assume we need to know whether or not 12 divides 6!.

1. Start by representing 12 as its prime factorization: $12=2^{2}\cdot 3^{1}$ .
2. Call get_powers(6, p), where $p\in \lbrace 2,3\rbrace$ 1. get_powers(6, 2) returns 4, so 2 appears in the factorization of $n!$ a greater number of times than it does in the factorization of 12.
2. Likewise, get_powers(6, 3) returns 2, which is greater than the number of times 3 appears in the prime factorization of 12.

After checking all the prime factors of 12 without any of them appearing more frequently than the same factors in the factorization of $n!$ , we find that 12 divides 6!

Gotchas

• Any points one can easily overlook?
• The correct way to understand ambiguous formulations?