On this Friday will take place Topcoder SRM 596.
GL & HF
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
How to solve the last problem efficiently?
How to solve 1000 div.2?
At first you've to notice that for F(n) be divisible by P, at least one part of the multiplication (n — i²) must be a multiple of P. So we have that n — i² (mod P) = 0 (mod P), so n (mod P) = i² (mod P). It's clear that i must be less than sqrt(n), so we can iterate over all possible i's and for each of them count how many n's exists that are less than some integer A. After some math it's clear that counting this is equal to (A — i²)/P. That's not the complete solution, since we're overcalculating some n's, and this occurs when we have some positive integer j different from i and less than sqrt(n) such that j² (mod P) = i² (mod P). Using an array or a set to mark for each i if i² module P has been already visited is enough.
Just calculate the answer for A being hi and subtract it from A being lo — 1 and you're done.
P.S: To better explain why (A — i²)/P, we know that n (mod P) = i² (mod P) and we can express it as n = i² + P*k. We know that n must be less than A, so i² + P*k < A, so k is actually the number of different solutions. Isolating k, we have:
P*k < A — i²
k < (A — i²)/P
k = floor((A — i²)/P)
My code: http://pastie.org/private/gltsff0nslzgn6cyqdexa
First Thanks for your neat explanation
Second In inequality you say k < (A — i²)/P not k <= (A — i²)/P
So what about if (A — i²)/P is integer like 12 so k<12 but
floor(12) is 12
So in this case k not less than (A — i²)/P but it equal to it
Third I want to learn how to reduce problem to equations like this do you have any advice or a how can I practice on this ?
Thanks
Editorial (complete)