Math Problem. Need Help

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hello everyone. I had doubts solving this problem. Since problem statement isnt that long, I decided to include it.

Nikhilesh loves factorials. One day he was working on exponents and starts wondering what would be the exponent of a number in the factorial of another number. He defines a function Exp(N,k) as:

Exp(N,k) = largest Y such that kY is a factor of N! .

He calculates Exp(N,k) for all values of k from 2 to N .

Since he is bad at remembering numbers, he computes the sum of Exp(N,k) for all k in range [2,N]. This sum is easy to remember.

Your task is to calculate this sum for a given value of N. Since the value can be large, print its modulus with mod (ans%mod).

I used miller rabin primarility test for generating primes. Then I factorised every number upto N, stored it in a place. Then I found out the frequency of each element and stored it along with that element in a pair. So I had all the prime factors and exponents of the factorial, which I used to solve the question.

However this is extremely slow for large input.

Any other feasible method ?

Thanks for help.

Link To Problem

Комментарии (6)

Написать комментарий?

porker2008

10 лет назад, # |

Did you mean k^Y?

→ Ответить

Na2a

10 лет назад, # ^ |

It's k^Y in the problem statement (hackerrank).

Any link to the problem statements in hackerrank?

Read topic carefully.

Thanks. I am not used to the hyperlink with no underline. :-p

ItsLastDay

← Rev. 2 →

Method is essentially the same: you factorize every number from 1 to N and do some calculations with frequencies.

However, N = 10⁷ hints us, that $\text{[math]}$ factorization is rather slow. Therefore, one should use sieve of Eratosthenes to precalculate smallest\largest prime, that divides every number. Here is a pseudocode (which I used during contest):

int largest[N]
fill 'largest' with zeroes
largest[1] = 1
for i in [2..N]:
  if largest[i] == 0: // 'i' is a prime number
    for j in [i:N] with step i:
      largest[j] = i;

Sieve works in $\text{[math]}$ or something like that. You can find out more about it on wikipedia.

The last part of solution is factorizing number, given an array 'largest'. It goes like this:

function factorize(n):
  factors = list()
  while n > 1:
    int factor = largest[n]
    n /= factor
    factors.add(factor)
  return factors

This method iterates on n's factors directly, so it works in p₁ + p₂ + ... + p_k moves, given that n = a₁^p₁a₂^p₂... a_k^p_k

Блог пользователя Fear_Is_An_Illusion