Qualified's blog

A problem I made but don't know how to solve
By Qualified, history, 23 months ago, In English

Find the number of positive integers that are $$$\le n$$$ and is coprime to $$$\text{lcm}(1, 2, 3, \dots, x)$$$ where $$$n$$$ and $$$x$$$ are positive integers. Maybe have $$$n\le 10^{15}$$$ and $$$x\le 10^{12}$$$.

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

Comments Comments (17)
| Write comment?
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the case where x > sqrt(n), the answer would just be the number of primes between x + 1 and n, since all numbers other than the primes can be written as P*Q (1 < P ≤ Q ≤ n), where P must be lower than sqrt(n) so it will not be coprime with the LCM. This is probably impossible to calculate for very large n so the limit for n should be lower, maybe around 10^6 or just make x ≤ sqrt(n) (I am not sure what happens in this case).

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

    For n <= 1e7, one possible solution is to find all primes larger than x and find all the numbers which have only them in their factorisation using sieve of erashosthens. This would yield a solution of O(n log log n).

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    You can find the number of primes up until N in something like O(N^(2/3)), so you this by itself isn't a reason to discard the possibility of having big N. https://codeforces.net/problemset/problem/665/F This is a related problem, there's some discussion about other approaches in the editorial and this is well known if you've wandered around project euler for long enough.

    That being said, I don't know how to solve the problem proposed here in lower than O(N).

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

      Thank you for the insight, I was not aware of this.

      → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it -55 Vote: I do not like it

I am not sure what you mean with lcm. Edit: Thanks for help I got it now .

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    $$$n≤10^{15}$$$ and $$$x≤10^{12}$$$.

    bruh

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have an idea which I thought on top of my head.

The $$$lcm(1, 2, \cdots x) = \prod\limits_{p \in primes}p^{max(k)_{p}}$$$. $$$max(k)_{p}$$$ is the largest power that satisfies $$$p^{max(k)_{p}} \le x$$$. Then, just subtract the number of multiples of $$$p^y$$$, $$$1 \le y \le max(k)_{p}$$$ in the range $$$[1, n]$$$, make sure to subtract each number uniquely by any technique. So, if you have a fast enough way to get the primes in the range $$$[1, x]$$$, I think that should be enough.

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

    If you subtract all the multiples of $$$p^k$$$, then you are undercounting because you subtract all multiples of $$$p$$$. But if you subtract all multiples of $$$p$$$, you are also subtracting multiples of other primes. So you have to do PIE, which probably won't be fast enough.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The tittle shows my whole life :)

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

Ok so I've figured out one way to solve this in $$$O(N^{2/3}logN + N/logN)$$$.

Basically, we'll have an array P of primes lesser than or equal to X and calculate a dp that'll solve the problem using PIE:

dp[i][j] = sum of (-1)^|s| for every subset s of primes in prefix of size i of P such that floor(N/product of si in s) = j

but instead of using that array like that, we'll process the primes over sqrt(N) by grouping them together by the floor of the division between N and them. This is the same idea as in the problem that I mentioned here https://codeforces.net/blog/entry/110878?#comment-987973. Using that problem's solution, we can solve this part in $$$O(N^{2/3} logN)$$$. We can do this because we can't use more than one such number otherwise their product will be larger than N. Then, what remains is the primes less than sqrt(N), there'll be $$$O(sqrt(N)/log(sqrt(N)))$$$ of those and we can simply find them and do the dp using two pointers to aid the transition to solve this last part in $$$O(number of primes * number of results for floor(N/i))$$$.

Edit: whoops. I was too stupid to think and just mechanically solved the problem. As dino_merlin mentioned, X being greater than sqrt(N) means just counting primes, so we can ignore everything that I mentioned here for that case. The remaining part for primes under sqrt(N) still stands.

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

    Hi tfg !

    It is bit confusing how time complexity of that dp is $$$O(numberofprimes * numberofresultsforfloor(N/i))$$$. With knapsack-like dp you will need $$$O(numberofprimes^2 * numberofresultsforfloor(N/i))$$$ for transition.

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

      Transition is O(1) due to "using a two pointers approach to aid the transition"

      → Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Maybe we can use the "Magic" tab in Codeforces?

→ Reply