hardik_836's blog

By hardik_836, history, 17 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it