Getting TLE on div2 codeforces

https://codeforces.com/contest/1372/problem/B
https://codeforces.com/contest/1372/submission/87037436

Read the editorial.

Before that be sure to read about time complexity. You should see how bad the brute force solution is.

sorry for that iā€™m newbie please suggest me atleast good brute force solution

In this question the brute force solution will give TLE, but brute force will be applied for one part. You have used lcm function inside your for loop which in turns uses the __gcd function, which has time complexity of O(log2n) and that is why it gives TLE as it exceeds O(n) complexity. Take some sample test cases by yourself and you will notice that for even values of n the answer is n/2 and n/2.
For odd n you have to apply a simple loop for checking its greatest divisor. Here I am attaching my solution. Hope it helps.
https://codeforces.com/contest/1372/submission/86615864

1 Like

thanks @devilamgs

1 Like