Help for Number Theory problem of today's Newton coding challenge

If someone participated in that contest and has solved the fifth problem please kindly share your approach.
Well right now the contest problems are not visible but they will be open soon.
Here goes the contest link : Newton School

And I m describing the problem statement :slight_smile:

given two numbers L and X ’

( 0<=L,X <=1e9) you have to count the number of pairs (A,B) such that

A<=B<=L and gcd (A,B)=X
time limit was 2secs

Well Euler Toutient function striked me and we were supposed to calculate

phi(1) +phi(2) +…+ phi(L/X) but doing it in NlogN and O(N) space complexity gave me MLE.

So can anyone please help .

Check this

yes I just checked the Cf blog and btw thanks a lot for the response