codeforces 679A A. Bear and Prime 100 (交互题,构造)

题目链接

题意:存在一个[2..100]之间的数,每次可以询问一个数是否是该数的因子,返回yes或者no,最多询问20次。每次要输出询问的数,以及最后要输出这个数是否是质数。

思路:第一次做交互题。。。发现完全不能按照以前的思路。。。

更像是相反的。。。把output看做某种输入。。。input里是某种结果。。。我要根据input里的东西来确定一些东西。

就是先有output,再有input。。。output是选手的输入(最后一个除外),input是返回结果(不是你写的代码的返回结果)

 

对于这道题。。我们要尽可能少得猜一个数的因子,以确定该数是否为质数。

一个数不是质数的话,就有至少两个大于1的因子。。。

很容易想到。。。判素因子。。。

由于至少有2个非1的因子才不是素数。。。最小为2,因此另一个因子不会大于50.。。

此外。。。有可能有两个相同质因数组成的因子。。。。

因此还要判一下2*2,3*5,5*5,7*7

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz