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,
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.
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.
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?