UVa 10110

From Algorithmist
Jump to navigation Jump to search

10110 - Light, More Light[edit]

Summary[edit]

Figure out how many times Mabu toggles the th switch to figure out whether the switch is on or not.

Explanation[edit]

There are a few things you should immediately notice:

  • Once Mabu has done his th walk, the th switch is never toggled again.
  • The answer is yes iff the th switch is toggled an odd number of times (otherwise, for each time it is turned on, it gets turned off, and is thus off in the end).
  • The th switch is toggled once for each factor of .

With this in mind, how can we tell if a number has an even or odd number of factors? For every factor has below it has one above . This suggests that unless is a perfect square, it has an even number of factors. So, the problem boils down to deciding if is a perfect square or not. Use your favorite math libraries to find the answer.

Implementation[edit]

  • 31-bit integer is not good enough for this problem. Use unsigned int.

Input[edit]

3
6241
8191
0

Output[edit]

no
yes
no

Solutions[edit]