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://mirror.codeforces.com/blog/entry/53925
Which easily leads to,
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.