# UVa 10110

Jump to navigation
Jump to search

## Contents

## 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