P2092 数字游戏

    • 75通过
    • 491提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 素数判断,质数,筛法
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    KC邀请他的两个小弟K和C玩起了数字游戏。游戏是K和C轮流操作进行的,K为先手。KC会先给定一个数字Q,每次操作玩家必须写出当前数字的一个因数来代替当前数字,但是这个因数不能是1和它本身。例如当前数字为6,那么可以用2,3来代替,但是1和6就不行。现在规定第一个没有数字可以写出的玩家为胜者。K在已知Q的情况,想知道自己作为先手能不能胜利,若能胜利,那么第一次写出的可以制胜的最小数字是多少呢?整个游戏过程我们认为K和C用的都是最优策略。

    输入输出格式

    输入格式:

    只包括一个正整数Q

    输出格式:

    第一行是1或2,1表示K能胜利,2表示C能胜利。

    若K能胜利,则在第二行输出第一次写出的可以制胜的最小数字。

    若是第一次就无法写出数字,则认为第一次写出的可以制胜的最小数字为0。

    输入输出样例

    输入样例#1: 复制
    6
    输出样例#1: 复制
    2
    输入样例#2: 复制
    30
    输出样例#2: 复制
    1
    6

    说明

    对于30%的数据,Q<=50;

    对于100%的数据,Q<=10^13。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。