| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
I was trying to code the problem Candies, yesterday and my logic was
In order to find a solution to
x + 2x + 4x ... = n
x(2^k — 1) = n
x = n / (2^k — 1 )
So I go through the factors of n in square root n time and check if they're of the same form as the denominator.
But apparently it times out, can someone shed some light on this?
Why iterate over factors of n? You know that answer exists, so just iterate over k from 2 to 31 and if the modulo is 0, print x corresponding to the k value.
Yes, I got that idea later but didn't change the code as I thought it would pass. My question was even though it isn't the most optimal complexity, it should squeeze through the TL ?
I would recommend using
__builtin_popcount(x) = 1to check for power of 2. Also n goes to 1e9 so your factorization works in 1e4, and for 1e4 test cases , complexity goes to nearly 1e8 , which is hard to squeeze in 1 sec.Your program run in $$$O(\sqrt{N})$$$ each test case. Because maximum $$$T$$$ is $$$10^4$$$ and $$$N$$$ is $$$10^9$$$, so it will run about $$$3*10^8$$$ operation which it make TLE (1 second = $$$10^7$$$ and I never try make $$$10^8$$$ operation with Time Limit 1 second). One another solution is iterate all k from 1 to $$$log2(n+1)$$$ so $$$n mod 2^k-1 = 0$$$ and you will find $$$x$$$. This complexity worth $$$O(log(N))$$$ for find $$$k$$$ each test case and run about $$$3*10^5$$$ operation with worst case.
Hope it's useful. Sorry for my bad English.