JZOJ__Day 5:【普及模拟】num

题目描述

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。
说明：若C能胜利，不用输出第二行，输出2即可。

样例输入

6

样例输出

2

数据范围限制

对于30%的数据，Q<=50; 对于100%的数据，Q<=10^13。

分析
这道题分为三种情况：
1：n为质数，writeln(1); write(0);
2：n为两个质数的乘积（两个质数可以相等），write(2)
3：n很复杂，则输出n最小的两个质因数（可以相等，即n=k*t*t， t为此质因数）的积

程序：

var i:longint; j,k,n,m,ans,num:int64;procedure aa; beginreadln(n);m:=n;for i:=2 to trunc(sqrt(n)-0.1) dowhile n mod i=0 dobeginn:=n div i;num:=num+1;end;if trunc(sqrt(n))=sqrt(n) then inc(num);n:=m;if num=0 thenbeginwriteln(1);writeln(0);haltend elseif num=1 then writeln(2) elsebeginans:=1;for i:=2 to trunc(sqrt(n)) dobegink:=0;while n mod i=0 dobegininc(k);n:=n div i;ans:=ans*i;if ans<>i thenbeginwriteln(1);writeln(ans);halt;end;end;end;end; end;beginassign(input,'num.in');reset(input);assign(output,'num.out');rewrite(output);aa;close(input);close(output); end.

转载于:https://www.cnblogs.com/YYC-0304/p/9500090.html

总结

以上是生活随笔为你收集整理的JZOJ__Day 5:【普及模拟】num的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。