shakil.ahamed's blog

Help: CodeChef D4 — Primes in the GCD table — reducing run time.
By shakil.ahamed, history, 6 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I will tell you a hint. Compute how many times you need to add some multiple of a number "d" to the answer. You may see a pattern.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think I am walking backward with your hint. Tried many possibilities. I can't get ride of the fact that K has to be a prime. Can you please write 1 step from where should I try?

    → Reply