### Tobby_And_Friends's blog

By Tobby_And_Friends, history, 20 months ago, ,

Problem name: Count LCM

Let's say n < m. Then the answer is for each integers i, from 1 to n, how many integers up to m are co-prime with i. I tried solving the problem but it got me a TLE. How do I optimize my solution? Any help is really appreciated.

•
• +5
•

 » 20 months ago, # |   0 Your solution has O(T * N) complexity. Worse case will give you about 10^3 * 10^6 = 10^9 operations of multiply and divide — is not so good.It can be seen, that there are only O(sqrt(N)) possible values of N / I and O(sqrt(M)) of M / i.For each test you can found segments [iLeft, iRight] for M, such that M / (iLeft - 1) > M / iLeft == M / iRight > M / (iRight + 1).Each segment adds to answer M / iLeft * sum(mu[iLeft] * N / iLeft, ..., mu[iRight] * N / iRight).Complexity of this solution is O(T * (N + sqrt(M)), if we use prefix sums for mu[i] * N / i (N for recalculating prefix sums). But it is even worse, than we had at the start!But we can use, that there are only O(sqrt(N)) possible values of N / i. We can use segment tree, that can do next operations: Set value x for each index k from [i, j]; Get sum of value[k] * mu[k] for k from [i, j]. We can set value N / iLeft for each segment [iLeft, iRight], such that N / (iLeft - 1) > N / iLeft == N / iRight > N / (iRight + 1).Complexity of this part is O(sqrt(N) * logN) and complexity of calculating answer is O(sqrt(M) * logN).Total complexity is O(T * (sqrt(N) + sqrt(M)) * logN). Worse case will give you about 10^3 * (10^3 + 10^4) * 20 = 2 * 10^8 operations, that can be acceptable.