UVa 10139

From Algorithmist

Contents 1 10139 - Factovisors 2 Summary 3 Explanation 4 Gotchas 5 Notes 6 Input 7 Output

[edit] 10139 - Factovisors

• http://acm.uva.es/p/v101/10139.html

[edit] Summary

Summary of the problem statement goes here.

[edit] Explanation

1. Simply any number can be represented as product of primes to powers:
2. 

So now only reprsent the second number (which will divide the factorial) and see if the powers of its prime less than the powers in the factorial.

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

1. Start for representing 12 as 12 = 2² * 3¹

Now call some function to tell you What is the power of a prime in factorial n;

int get_powers(n, p)

now calling once for 2 we get that 6! has 2⁴ Where 4 is great than 2 (2² < 2⁴)

now calling once for 3 we get that 6! has 3² Where 2 is great than 1 (3¹ < 3²)

After finishing all the powers of 12 without any problems 12 divides 6!

[edit] Gotchas

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

[edit] Notes

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

[edit] Input

6 9
6 27
20 10000
20 100000
1000 1009

[edit] Output

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