Блог пользователя Qualified

Автор Qualified, история, 22 месяца назад, По-английски

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}$$$.

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.me/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).

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится -55 Проголосовать: не нравится

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

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The tittle shows my whole life :)

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

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.me/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.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
22 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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