A8975. Game with Powers
编程题
普及/提高-
知识点
题目描述
Vasya and Petya wrote down all integers from $1$ to $n$ to play the "powers" game ( $n$ can be quite large; however, Vasya and Petya are not confused by this fact).
Players choose numbers in turn (Vasya chooses first). If some number $x$ is chosen at the current turn, it is forbidden to choose $x$ or all of its other positive integer powers (that is, $x^{2}$ , $x^{3}$ , $...$ ) at the next turns. For instance, if the number $9$ is chosen at the first turn, one cannot choose $9$ or $81$ later, while it is still allowed to choose $3$ or $27$ . The one who cannot make a move loses.
Who wins if both Vasya and Petya play optimally?
Players choose numbers in turn (Vasya chooses first). If some number $x$ is chosen at the current turn, it is forbidden to choose $x$ or all of its other positive integer powers (that is, $x^{2}$ , $x^{3}$ , $...$ ) at the next turns. For instance, if the number $9$ is chosen at the first turn, one cannot choose $9$ or $81$ later, while it is still allowed to choose $3$ or $27$ . The one who cannot make a move loses.
Who wins if both Vasya and Petya play optimally?
输入格式
Input contains single integer $n$ ( $1<=n<=10^{9}$ ).
输出格式
Print the name of the winner — "Vasya" or "Petya" (without quotes).
输入输出样例
输入 #1
1
输出 #1
Vasya
输入 #2
2
输出 #2
Petya
输入 #3
8
输出 #3
Petya
说明/提示
In the first sample Vasya will choose 1 and win immediately.
In the second sample no matter which number Vasya chooses during his first turn, Petya can choose the remaining number and win.
In the second sample no matter which number Vasya chooses during his first turn, Petya can choose the remaining number and win.