Yet Another Blog

Problem

PKU – 1401

Given a (large) integer K, find the number of zeros on the right of the factorial of K. For example, factorial 15 = 1,307,674,368,000, so the number of zeros on right of the factorial (let’s denote it Z(1,307,674,368,000) ) equals 3.

The input integer K can be as large as 1000,000,000.

Solution

Given an integer N, let the prime factorization of N be .

The number of zeros on the right of N, that is Z(N), is simply the number of times N can be divided by 10 without getting a fraction. It is obvious that .

Since N, in our case, is the factorial of another integer, K, then the prime factorization of N is just the product of the prime factorizations of all the integers from 1 to K inclusive. This can be written as

So, and .

Consequently,

In other words, that is the minimum between the sum of the number of times 2 has appeared as a factor for all integers in the range 1 through K versus the sum of the number of times 5 has appeared as a factor for all integers in the same range. Obviously the number of times 5 has appeared is smaller, because it appears every 5 integers, versus 2 in the case of 2. So actually we are interested in .

We might go through all the integers in the range 1 to K and find, for each integer in such range, how many times 5 appears as a factor. But due to the fact that we are dealing with large integers that won’t be feasible. Alternatively, we may solve it as follows: the integer division K/5 gives us the number of integers in the range 1 through K for which 5 is a factor at least once, K/25 gives the number of integers in the same range for which 5 is a factor at least twice, … and so on.

Consequently, , where the division is integer division.

The formula is logarithmic in the value of K, so it is linear in the number of bits. That is efficient enough to handle the required input.

Problem:

PKU – 3604

Given an integer N, find all the factors of N including the trivial factors (1 and N). For each factor f, find the cube of the number of factors of  f. Then sum all those cubes.

For example, if N=4, the set of all possible factors are 1, 2 and 4. 1 has only one factor which is 1. 2 has 2 factors: 1 and 2. 4 has 3 factors: 1, 2 and 4. So the result equals

Solution:

A naive solution won’t work since the input is too large (up to 500,000 test cases and N can be as large as 5,000,000).

The idea is as follows: According to the fundamental theorem of arithmetic, any integer N>1 has a unique prime factorization (i.e., there is one and only one way to factorize this integer into a product of prime numbers).  For example, 420 has the following unique prime factorization:

420 = 2 * 2 * 3 * 5 * 7

For a given integer N, let the prime factorization of N be where n is the number of prime factors of N, is the distinct prime factor which is raised to the power .

We can see that the total number of general factors of N (all factors, not only the primes) equals .

This value follows from the fact that any general factor of N is just the product of some of the prime factors of N. So any such general factor has the prime factorization where . The case where for all i will give us the general factor . The case where for all i will give us the general factor   (the number itself).

However, we are not interested in the number of general factors of N; we are interested in the number of general factors of each general factor of N (!!) to be cubed each and summed together.

This value can be obtained as follows: using the same reasoning mentioned above, for each general factor of N, the number of general factors of equals . For each j and i, the value of ranges from 0 to inclusively, therefore the required value, the summation of cubes of numbers of general factors of all general factors of N, equals:

Re-distributing the summation we get the following formula:

Using the well-known series we can re-write our formula again as follows:

Thus, all we need to calculate is the prime factorization of N, from which we can get the value of for each i.

Necessary Optimizations:

Due to large input sizes, calculating the prime factorization of every input value from the scratch will give TLE. The process can be optimized by using simple dynamic programming.

For every integer N, the value we need to calculate is

where N’ is some integer less than N. So actually we can re-use the values of res( ) computed for smaller input values to compute larger ones. All we need for any given integer N is to find one of its  values (the power of one of its prime factors), then we can calculate res(N) recursively, and there comes dynamic programming.

Finding a power of one of the prime factors of N can be done easily once the prime factor itself is found. We can use a modified version of Sieve of Eratosthenes to find a prime factor for each integer in a given range.

The original Sieve was used to determine which natural numbers are prime and which are not, up to some maximum number MAX.   Starting from counter=2, we mark all multiples of the counter as not-prime until MAX is reached. Move the counter forward to the next unmarked integer (which will always be prime since it is not a multiple of any smaller integer).

In the modified version, instead of marking the multiples of the counter as not-prime, we will associate the counter with its multiples as a prime factor of them. This way we get a prime factor for each natural number up to MAX (which equals 5,000,000 is our case).

Having reached such step, dynamic programming can be done easily by iterating through natural numbers up to MAX, for each natural number N, we can calculate res(N) using the prime factor of N we have obtained before and res(N’) for some smaller natural number N’ also calculated before.