題目描述

KC邀請(qǐng)他的兩個(gè)小弟K和C玩起了數(shù)字游戲。游戲是K和C輪流操作進(jìn)行的，K為先手。KC會(huì)先給定一個(gè)數(shù)字Q，每次操作玩家必須寫(xiě)出當(dāng)前數(shù)字的一個(gè)因數(shù)來(lái)代替當(dāng)前數(shù)字，但是這個(gè)因數(shù)不能是1和它本身。例如當(dāng)前數(shù)字為6，那么可以用2,3來(lái)代替，但是1和6就不行?，F(xiàn)在規(guī)定第一個(gè)沒(méi)有數(shù)字可以寫(xiě)出的玩家為勝者。K在已知Q的情況，想知道自己作為先手能不能勝利，若能勝利，那么第一次寫(xiě)出的可以制勝的最小數(shù)字是多少呢？整個(gè)游戲過(guò)程我們認(rèn)為K和C用的都是最優(yōu)策略。

輸入

只包括一個(gè)正整數(shù)Q

輸出

第一行是1或2,1表示K能勝利，2表示C能勝利。
若K能勝利，則在第二行輸出第一次寫(xiě)出的可以制勝的最小數(shù)字，若是第一次就無(wú)法寫(xiě)出數(shù)字，則認(rèn)為第一次寫(xiě)出的可以制勝的最小數(shù)字為0。
說(shuō)明：若C能勝利，不用輸出第二行，輸出2即可。

樣例輸入

6

樣例輸出

2

數(shù)據(jù)范圍限制

對(duì)于30%的數(shù)據(jù)，Q<=50; 對(duì)于100%的數(shù)據(jù)，Q<=10^13。

分析
這道題分為三種情況：
1：n為質(zhì)數(shù)，writeln(1); write(0);
2：n為兩個(gè)質(zhì)數(shù)的乘積（兩個(gè)質(zhì)數(shù)可以相等），write(2)
3：n很復(fù)雜，則輸出n最小的兩個(gè)質(zhì)因數(shù)（可以相等，即n=k*t*t， t為此質(zhì)因數(shù)）的積

程序：

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.

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9500090.html

總結(jié)

以上是生活随笔為你收集整理的JZOJ__Day 5:【普及模拟】num的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。