Blue Flag, White Flag
InterviewTime limit1sMemory limit128 MB
Each of N players flips every flag whose number is a multiple of their index; count how many flags end white side up.
- Level
Easy3 of 10
- Topics
- Math, Number theory, Implementation, Brute force
- Solved
- No attempts yet
Problem
A flag flipping game is under way at the sports day held by the college student council. The software department and the ICT convergence department take turns playing. The rules are simple. The department whose turn it is sends out players. On the table in front of them sit flags numbered to , each lying blue side up and white side down.
The first player turns over every flag whose number is a multiple of . The second player turns over every flag whose number is a multiple of . In the same way, the -th player turns over every flag whose number is a multiple of , and the game ends once the -th player is done.
With players and flags, count the flags lying white side up after the -th player has finished.
Input
The first line contains , the number of players and also the number of flags. ()
Output
Print on the first line the number of flags lying white side up after the -th player has finished.
Hint
Take . Flags , , are on the table and three players take part. The first player turns over every flag whose number is a multiple of , so all three flags, blue side up at the start, end up white side up. The second player turns over flag , the only multiple of , leaving the flags white, blue, white. The last player turns over flag , the only multiple of , leaving them white, blue, blue. One flag lies white side up.