Tobby_And_Friends's blog

Number Theory Problem from UVA (UVA 12888 Count LCM)
By Tobby_And_Friends, history, 8 years ago, In English

Problem name: Count LCM

Link: https://uva.onlinejudge.org/external/128/12888.pdf

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.

Solution Link: http://ideone.com/mMoWMS

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

Comments Comments (9)
| Write comment?
»
8 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

I think the solution starts here:

Think about a prime i, the answer will be m-m/i (the total less the number of multiples of i)

Now think about a composite i. I'll use as example 6. The answer is m-m/2-m/3+m/6. The answer is the same for 12.

So, you have a composite number that has factorization p1^c1*p2^c2...pk^ck, the answer for this number will be the same answer as the answer for the highest square-free number that divides this number (p1*p2*p3..*pk) because a number isn't coprime with another if and only if they share at least one prime factor. So the answer will be: m-m/p1-m/p2...-m/pk+m/(p1*p2)+m/(p1*p3)...+m/(p1*pk)-m/(p1*p2*p3).

You go through all the divisors and where there's an odd number of prime factors, you subtract. Otherwise you add. You can modify the sieve to group the numbers by their square-free factorization on the sieve and also get how many primes there are on the factorization.

Now you'll have a vector ans[n+1] that's initialized to 0. Do this for 1<=i<=n

If i==square_free[i], for j in divs[i] make ans[i]+=((-1)^primes[j])*m/(j)

total_ans+=ans[square_free[i]]

where square_free[i] is the highest square-free number that divides i, primes[i] is the number primes that divide i and divs[i] is the numbers that divide i.

I'm not sure about the complexity of this, but it is slightly better than the usual O(n*logn). It looks like you are doing this but you aren't grouping the numbers by their square-free factorization, so you recalculate it a lot.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

there's no reason to use sieve, replace it with naive factorization

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

  1. Set value x for each index k from [i, j];
  2. 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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually it seems, that solution with logN is TL too.

    But we can remove logN from complexity, if we use 2 pointers idea: 1. Pointer to the current segment for M; 1. Pointer to the current segment for N;

    Move pointer[m] to the next "M-segment" [iLeft; iRight] and move pointer[n] over all "N-segments" included in [iLeft; iRight] — for each segment we can calculate sum in O(1), using prefix sums for mu[i].

    If we iterate over all segments in increasing order (we can calculate them in O(sqrt(N)) and O(sqrt(M)) in sorted order), our total complexity will be O(sqrt(N) + sqrt(M)).

    So total complexity is O(T * (sqrt(N) + sqrt(M)), that seems to be enough for this problem.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Have you noticed that the time limit for this is 10 seconds?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        PDF with problem statement doesn't include information about TL, so I thought about usual 1-2 seconds time limit.

        But I think, that it is better to know ways to solve problem with constraints as high as possible, because you can meet some harder problems, where these ideas could be only way to solve in time limit.

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, I send solution from link, it get AC with 3.12 seconds.

        So I think, that Tobby_And_Friends wants to know about some more faster ways of solving this problem than O(T * N).

        → Reply