PKU Candy Distribution

This is about number theory and I like these kinds of problems:

http://poj.org/problem?id=3372

Since in the problem, N is quite large, you need some analysis to solve it in a given time.

The first observation is how the number would increment if you thought it in the linear system, not in the circular system.

0, 1, 3, 6, 10, 15, 21, 28, ....

It's obvious that the sequence above is sums of an arithmetic sequence, more specifically you'll notice that p(i) = i * (i+1) / 2.

The second observation is its cycle. In modular arithmetic, there's almost always some cycle. Notice that the differences of the sequence above is 1, 2, 3,...., so the minimum possible cycle, --what we are discussing here is the cycle of jumping--, is n, since 0, 1, 2,...n-1 is equivalent to n, n+1, n+2, ... , 2n-1 in the modulo n.

Now the hardest part -- at least in my case--. The cycle of jumping is n as I explain above. So what's the cycle of position. The cycle of this system is the gcd of these two cycles.

Let's consider it by separating two situations: when n is odd, and n is even.

When n is odd, p(n) = n * (n+1) / 2. Since (n+1) is dividable by two, p(n) = 0 (mod n).

While when n is even, p(n) = n * (n+1)/2 = n/2 * n + n/2 = n/2 (mod n).

So the cycle of position is n and 2*n, for an odd number n and an odd number n, respectively.

So it's enough to think just 2*n moves, but it's still a big number -- the biggest possible number is 10^9--, and more analysis is required.

Let's consider when n is odd. p(0) = 0, and p(n-1) = (n-1) * n/2 = 0 (mod n). So for i in {0, 1, 2, ..., n-1}, two number, 0 and n-1, have the same value when mapped onto p. It's impossible to cover all numbers on p with {0, 1, ... n-1}. And since the cycle for odd numbers is n, we can say that the answer for test cases where n is an odd number is "No".

How about when n is even? As discussed in the previous paragraph, p(n) = n/2 (mod n). So for i in {n, n+1, n+2, ....., 2*n-1}, p(i) covers the opposite side of number set against {p(i) | i in {0, 1, ...n-1} }. Therefore it's possible to cover all the numbers if p(n/2) covers all the numbers.

We come to a conclusion that the answer ret(n) is:

"Yes" when n is 1,

"No" whe n is an odd number,

ret(n/2) when n is an even number.

Which comes down to the fact the answer is "Yes" if and only if n is two to the power of i, i = 0, 1, 2,.... . The implementation is pretty easy. Just count the bit set to 1. You can use __builtin_popcount() or n & (n-1) (*).

(*) n & (n-1) sets the LSB of n to zero. In this manner, n & (n-1) is zero iff n is two to the power of i.