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}$$$.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 165 |
2 | maomao90 | 163 |
2 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
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}$$$.
Name |
---|
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).
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).
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).
Thank you for the insight, I was not aware of this.
I am not sure what you mean with lcm. Edit: Thanks for help I got it now .
$$$n≤10^{15}$$$ and $$$x≤10^{12}$$$.
bruh
parallel computing with 1000+ machines
So that's you who has caused the global warming??
Not even 1000000000 machines would work for mari_kadi's idea
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.
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.
The tittle shows my whole life :)
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.
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.
Transition is O(1) due to "using a two pointers approach to aid the transition"
Ah i see
Maybe we can use the "Magic" tab in Codeforces?