My solution is to count the divisors of (a*b)^2 but a, b <= 1e6. In addition the problem has testcase <= 1e6. Can you help me?
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 160 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 151 |
My solution is to count the divisors of (a*b)^2 but a, b <= 1e6. In addition the problem has testcase <= 1e6. Can you help me?
Name |
---|
since a and b are both less than 1e6, so I guess you can use sieve.
edit:
precomputation is around O(N) with a tiny constant factor (with euler sieve), as mentioned by MatrixGroup.
Each query is thus O(log(N)) since we need to iterate through all of the prime factors of the number. Total time complexity then would be O(N+Q*log(N)), which I guess should be well within TL. :D
sorry for my horrible grammar and really, way too many revisions.
i tried using it but it time!
Well the algorithm should get accepted because the time complexity is O(Q log N), maybe your implementation has some problems that made it TLE
Obviously a number less than $$$10^6$$$ has at most $$$7$$$ distinct prime divisors. Let's denote $$$d=7$$$.
We can precompute the prime factorizations of numbers ranging from $$$1$$$ to $$$v=10^6$$$ in $$$O(vd)$$$ by Euler sieve.
We can know the factorization of $$$(ab)^2$$$ easily by the factorizations of $$$a$$$ and $$$b$$$.
Then we can know the number of divisors easily, which is sufficent enough to process $$$t=10^6$$$ queries.
Time Complexity: $$$O(vd+td)$$$.
Rwxy's solution is slightly different: he precomputes the smallest divisor instead of the whole factorization, and recompute the factorization for every query. The complexity, as mentioned by him, is $$$O(v+t\log v)$$$.
We can optimize it to $$$O(v+td)$$$ by precomputing the smallest divisor $$$p$$$, the power of that $$$k$$$, and the next number(that is the number divided by $$$p^k$$$), that makes it faster.
thanks for telling me about the optimization!
You're welcome. That also optimizes my solution because $$$v$$$ (your $$$N$$$) can be set up to $$$5\times10^7$$$ and $$$t$$$ (your $$$Q$$$) can be set up to $$$5\times10^6$$$. (assuming around $$$10^8$$$ calculations per second)
How to sieve with the complexity is O(log n)
What do you mean by sieve? If you mean "recompute the factorization", we repeat dividing the number with the smallest prime divisor until it becomes $$$1$$$.
Is my solution to this problem need to be optimized anymore? I think my method is so optimal
It is able to pass the problem, but not optimized. Your solution is $$$O(v\log v+q\log v)$$$, and can be optimized to $$$O(v\log \log v+q\log v)$$$ by replacing
if(prime[i])
toif(prime[i]==i)
.If there's something wrong, remind me.
whether the sieve of Eratosthenes or euler better ? should I replace my sieve with euler for better optimization. Can you show me how to optimize even more! If(a, b <=1e9) what should i do?
Euler sieve is $$$O(v)$$$, while Eratosthenes sieve is $$$O(v\log \log v)$$$. About the best solution I can come up with, I mentioned it above. I cannot solve the case where $$$a,b\le 10^9$$$.
Why is "The number of solutions for the equation" equal to "Number of divisors of (a*b)^2 " ?
Rewriting the equation, we get $$$(x - ab)(y - ab) = a^2b^2$$$, and clearly, $$$x$$$ and $$$y$$$ must be positive, so the number of solution is simply $$$d(a^2b^2)$$$. AMC level algebraic manipulation I would say
If we have the prime factorization of $$$N$$$, then we can easily calculate the number of factors $$$N^2$$$ as power of each prime will be doubled. So, now the question is to get the prime factorization of $$$a*b$$$. For this we can separately factorize both $$$a$$$ and $$$b$$$ and keep the count of their primes in one $$$map$$$ using sieve.
My implementation using sieve is here .
A similar question can be found here .
i can using unordered_map!
Yes you can.