C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1536 不一样的猜数游戏

Problem

瓦斯亚和皮台亚在玩一个简单的游戏。瓦斯亚心中想一个整数x,它是1到n之间的整数。然后皮台亚尝试着猜这个数字。

皮台亚每次问一个形如这样的问题:这个x是y的倍数吗?

这个游戏的流程是这样的:首先皮台亚把所有他想问的形如上述的问题都问出来(当然他也可以不问任何问题),然后瓦斯亚针对每一个问题给出yes或no的答案。最后皮台亚根据这些问题推断出瓦斯亚心中所想的x是哪个数字。

现在皮台亚想知道他最少要问多少个问题才能猜出1到n之间的那个数字。也就是说不管x是1到n之间的哪个数字只要问那些问题就能够确定那个数字了。

样例解释:

可以问是否是2,3,4这些数字倍数的三个问题。

如果都不是,说明是1.

如果是4的倍数,说明是4.

如果是3的倍数说明是3.

否则就是2。

没有比这更少的问题数目了。

Solution

n以内所有质数以及他们不超过n的次方都要问。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<string.h>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int n;
const int MAXN=1e3;
bool ipr[MAXN+20];
int cnt,pri[MAXN/5];
void prime(){//∞£ Ω…∏∑®
int N=sqrt(MAXN)+0.5,mul;
memset(ipr,true,sizeof(ipr));
ipr[1]=false;
for(int i=2;i<=N;i++){
if(ipr[i]==true){
i==2?mul=1:mul=2;
for(int j=i*i;j<=MAXN;j+=i*mul){
ipr[j]=false;
}
}
}
for(int i=2;i<=MAXN;i++){
if(ipr[i]==true){
pri[++cnt]=i;
}
}
}
int ans;
int main(){
prime();
io_opt;
cin>>n;
for(int i=1;i<=cnt&&pri[i]<=n;i++){
int cur=1;
while(1){
cur*=pri[i];
if(cur<=n) ans++;
else break;
}
}
cout<<ans<<endl;
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/26359/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!