As you know that Educational Codeforces Round 54 (Rated for Div. 2) was held yesterday. Perhaps, you solved 1076B - Divisor Subtraction without any difficulty. Now, I am thinking how to solve this problem if there are no less than 10^5 queries. Please, mention the complexity with approach.
| # | User | Rating |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 142 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 8 | maroonrk | 132 |
| 10 | qwexd | 129 |
owowow
Any idea? Then, share with me.
Yes
Share your idea, please.
if you lower the limit of n to 1e7 than you can have as many queries as you want, but i dont think 1e10 is gonna do well for more than 100 queries...
There are around 1e4 primes lesser than 1e5 so you can optimize it to work for around 1e4 queries (and maybe faster with pollard rho?)
That is impossible to do so in time limit of 2 or 3 seconds, isn't it?
A simple 1e8 loop runs under 1 second easily in codeforces.
Has there any way to find at least a divisor of n smaller than sqrt(n) within at most 1000 loops where n<=10^10?
Isn't this question equivalent to integer factorization at the worst case? Then, I suppose there are no known way to do the task in 1000 loops...
I thaught that also...whatever,thanks bro....
As tfg mentioned above, for a lot of queries, to precompute all the primes in range [2, 1e5] would be fastest. Then your task must cost at most
which is larger than 1000