# Difference between revisions of "UVa 10139"

From Algorithmist

m (Relink to new archive.) |
|||

Line 46: | Line 46: | ||

1009 does not divide 1000! | 1009 does not divide 1000! | ||

</pre> | </pre> | ||

+ | == Solutions == | ||

+ | * [http://codealltheproblems.blogspot.com/2015/06/uva-10139-factovisors.html Code All the Problems] | ||

[[Category:UVa Online Judge|10139]] | [[Category:UVa Online Judge|10139]] | ||

[[Category:Math]] | [[Category:Math]] | ||

[[Category:Number Theory]] | [[Category:Number Theory]] |

## Latest revision as of 08:24, 7 July 2017

## Contents

## 10139 - Factovisors[edit]

## Summary[edit]

Summary of the problem statement goes here.

## Explanation[edit]

- Any number, , can be represented as product of powers of primes: . This is called the "prime factorization" of .

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, , in can be found using:

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

- Start by representing 12 as its prime factorization: .
- Call get_powers(6, p), where
- get_powers(6, 2) returns 4, so 2 appears in the factorization of a greater number of times than it does in the factorization of 12.
- 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 , we find that 12 divides 6!

## Gotchas[edit]

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

## Notes[edit]

- 0 divides n! is false.
- m divides n! is true if

## 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!