1 Like
Have you read the editorial?
In editorial, explanation is not there(images are not loading).
Hi, I’ll comment my explanation to the editorial by today.
At the first glance of this problem, I planned to ignore the constraint and get the sum of all the lcm first. Then subtract the sum of lcm over the ones for which some [n^2 | gcd(a, b)]. But at the end, I found the second problem is harder. I don’t even know how to integrate it into the formula in a practical way.
Do you have any idea on if it is indeed much harder? or it actually can be solved in a reasonable time complexity.