Talk:UVa 10139

From Algorithmist
Jump to: navigation, search


Can anybody please write UVa problem 10139 -- Factovisors? I could find a lot of test data in the UVa forums but that's not much help. Looks like some overflow issues that I am not able to correct.

You can get away with it by using ints, at least for me. My algorithm is O( N^1/2 ), where N is size of the divisor. You got all your special cases? Larry 22:33, 24 May 2006 (EDT)

The method I used was: Sieve until 1<<16, store them in an array. For each prime which is a factor of divisor d: find what max power of prime p divides d (say a). Then find out the max power of p that divides n! (say b). If b >= a for all prime factors of the divisor d, then d divides n! otherwise not. I checked for cases when d = 0, d = 1, n = 0. Anything else I should check it for?--Shalinmangar 01:49, 25 May 2006 (EDT)

My algo was even more naive than that - it doesn't sieve.. it sounds about right though.. Larry 15:36, 25 May 2006 (EDT)