How I can Find smallest Odd Prime factor of n
n<=10^18
we have test cases 10^5
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 152 |
10 | maroonrk | 151 |
How I can Find smallest Odd Prime factor of n
n<=10^18
we have test cases 10^5
Name |
---|
Hi, just factorize n and choose the smallest factor, you can use Pollard's rho algorithm
I think it gets TL because of many test cases
I don't think there is a way that doesn't involve factorization since the prime factors for a composite number could be as large as $$$10^9$$$.
Pollard Rho is typically $$$\mathcal{O}(\sqrt{\text{smallest prime factor}})$$$ though. Since the input might itself be prime, Miller Rabin to first check primality, followed by Pollard Rho if the number if composite should be sufficient.
Problem link?
Problem
$$$ n \equiv k*(k-1)/2 \mod{k} $$$
$$$ 0 \equiv 0 \mod{k} $$$
I don't think a div-1 + div-2 D would require to solve the exact prblm that you mentioned in the blog ,probably it will require something else , observe better
if there is another easier sol...can you give me a small hint
You found that the equation $$$n \equiv \frac{k(k+1)}{2} \bmod k$$$ must be satisfied for a good $$$k$$$. Is this a sufficient requirement, i.e. is every $$$k$$$ satisfying this also good? Or are there other requirements for a good $$$k$$$? You should try to find sufficient conditions for a good $$$k$$$, preferrably in the form of mathematical equations, and try to find something by playing around with the equations. I can also give more specific hints if you want more help.