UVa 10139

From Algorithmist
Jump to: navigation, search

10139 - Factovisors[edit]

Summary[edit]

Summary of the problem statement goes here.

Explanation[edit]

  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:

int get_powers(n, p)

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[edit]

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

Notes[edit]

  1. 0 divides n! is false.
  2. m divides n! is true if m\leq n

Input[edit]

6 9
6 27
20 10000
20 100000
1000 1009

Output[edit]

9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!

Solutions[edit]