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

Revision en2, by shakil.ahamed, 2018-07-29 00:17:13

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.net/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.

Tags mobius function, #number theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English 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 English shakil.ahamed 2018-07-29 00:12:39 783 Initial revision (published)