Math Problem. Need Help

№	Пользователь	Рейтинг
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

№	Пользователь	Вклад
1	awoo	161
2	maomao90	160
3	adamant	156
4	maroonrk	153
5	-is-this-fft-	148
5	atcoder_official	148
5	SecondThread	148
8	Petr	147
9	nor	144
9	TheScrasse	144

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

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

Did you mean k^Y?

→ Ответить

Na2a

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

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