Help: CodeChef D4 — Primes in the GCD table — reducing run time.

Правка en1, от shakil.ahamed, 2018-07-29 00:12:39

Problem: https://www.codechef.com/problems/D4
Submission: https://ideone.com/fuoYkk

The problem asked how many gcd(i, j) are prime, where 1 <= i <= a, 1 <= j <= b.

This is the first time I am studying mobius inversion. I modeled the problem as of many example given in: https://codeforces.me/blog/entry/53925

Which easily leads to,

where, m = min(a, b)

This requires 3 * 107 iteration for worst case. Due to tight time limit, this is huge. But I can't reduce it any further. Any hint will be helpful.

Теги mobius function, #number theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский shakil.ahamed 2018-07-29 00:17:13 2 Tiny change: 'm_{d=1}^{m} \mu(d) \' -> 'm_{d=1}^{m/k} \mu(d) \'
en1 Английский shakil.ahamed 2018-07-29 00:12:39 783 Initial revision (published)