Win or Freeze

题意翻译

题目大意: 给定一个数字q,如果它有非1或本身的因子,则称这个数字是可操作的. 定义操作如下: 将这个数字除以它的一个非1或本身的因子 现在有玩家1和玩家2,他们玩了这样一个游戏: 两人轮流对这个数进行操作,直到不能操作这个数字的玩家获胜.(假设玩家的所有操作都是最理想的) 输出: 第一行输出获胜玩家:1(或者2) 玩家1获胜则还要在第二行输出一个玩家1能在第一次操作中选择的数,若玩家1一开始就不能操作,第二行输出0; 数据范围: 1<= q <= 1e13; 样例解释: 输入12,此时12的因子有1,2,3,4,6,12 则玩家1第一次可以选择的数有:2,3,4,6 此时玩家1选择q除以数字3必胜(因为剩下4,而玩家2此时只能选择2,剩下2,玩家1胜) 则此时的样例输出是: 1 3 感谢@dogewww 提供翻译

题目描述

You can't possibly imagine how cold our friends are this winter in Nvodsk! Two of them play the following game to warm up: initially a piece of paper has an integer $ q $ . During a move a player should write any integer number that is a non-trivial divisor of the last written number. Then he should run this number of circles around the hotel. Let us remind you that a number's divisor is called non-trivial if it is different from one and from the divided number itself. The first person who can't make a move wins as he continues to lie in his warm bed under three blankets while the other one keeps running. Determine which player wins considering that both players play optimally. If the first player wins, print any winning first move.

输入输出格式

输入格式

The first line contains the only integer $ q $ ( $ 1<=q<=10^{13} $ ). Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

输出格式

In the first line print the number of the winning player ( $ 1 $ or $ 2 $ ). If the first player wins then the second line should contain another integer — his first move (if the first player can't even make the first move, print $ 0 $ ). If there are multiple solutions, print any of them.

输入输出样例

输入样例 #1

6

输出样例 #1

2

输入样例 #2

30

输出样例 #2

1
6

输入样例 #3

1

输出样例 #3

1
0

说明

Number $ 6 $ has only two non-trivial divisors: $ 2 $ and $ 3 $ . It is impossible to make a move after the numbers $ 2 $ and $ 3 $ are written, so both of them are winning, thus, number $ 6 $ is the losing number. A player can make a move and write number $ 6 $ after number $ 30 $ ; $ 6 $ , as we know, is a losing number. Thus, this move will bring us the victory.