Maybe it’s because you’re using endl.
The TL is 3s. Worst case (3×10^8) should easily pass within this limit.
Actually, your solution fails when there are around 100 cases with small numbers and also when there are around 100 cases with 1000 numbers that are ~10^7 and have a large number of factors. These solutions don’t pass even in double TL (6s).
No still showing TLE
Finally AC, used unordered map and “\n”
But we can perform 10^6 operations in one second, right?
nope. ~3×10^8 iterations pass in 1s in modern judges
1 Like
This is because you are running O(\max(A) \log N) for like 100 tests, which would definitely time out. O(N \sqrt{\max(A)}) has the guarantee that sum of N over all cases is at most 10^5.
gcd(b+kl,l) = gcd(b,l)
Can someone explain why this is true?
Same here dude
because kl is multiple of l so gcd(b,l) will also divide b + kl
It’s based on Euclid’s gcd algorithm
If a>b>0 then gcd(a,b) = gcd(a-b, b)
Here, b+kl > l so gcd(b+kl, l) = gcd(b+kl-l, l) = gcd(b+kl-2l, l) = … = gcd(b, l)
1 Like