打卡信奥刷题（2544）用C++实现信奥 P2092 数字游戏

P2092 数字游戏

题目描述

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

输入格式

仅一行，一个正整数QQQ。

输出格式

第一行是111或222，111表示 K 能胜利，222表示 C 能胜利。

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

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

输入输出样例 #1

输入 #1

6

输出 #1

2

输入输出样例 #2

输入 #2

30

输出 #2

1 6

说明/提示

对于30%30 \%30%的数据，Q≤50Q \le 50Q≤50；
对于100%100 \%100%的数据，2≤Q≤10132 \le Q \le {10}^{13}2≤Q≤1013。

C++实现

#include<cstdio>#include<cstring>#include<algorithm>#include<queue>usingnamespacestd;typedeflonglongll;//注意一定要long long类型ll n,ans;queue<ll>q;intmain(){scanf("%lld",&n);for(ll i=2;i*i<=n;i++)while(n%i==0)q.push(i),n/=i;//分解质因数if(n!=1)q.push(n);//加入最大的因子if(q.size()==2)printf("2\n");elseif(q.size()==1)printf("1\n0\n");else{printf("1\n");ans=q.front();q.pop();printf("%lld\n",ans*q.front());}//分类讨论，具体见上return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容