In the recent contest Codeforces Round #841 (Div. 2) and Divide by Zero 2022 I am not able to understand how we calculate number of pairs (x,y) where 1≤x<y≤n with gcd(x,y)=k for each k∈[1..n] in O(nlogn) time. In the tutorial it is stated we use mobius function/dynammic programing approach to calculate it.