Vasya and Petya's Game 

---

 

Mean: 

给定一个n，系统随机选定了一个数x，(1<=x<=n)。

你可以询问系统x是否能被y整除，系统会回答"Yes"or“No"。

问：至少询问多少次可以唯一确定x，并输出询问序列。(special judge).

analyse:

做法：求质数的整数次幂（不大于n）。

思路：首先我们肯定是用质数来判断，因为质数排除的是最多的。

如果质数p[i]能够整除，那么x有可能是p[i]^2,p[i]^3....。

Time complexity: O(N)

 

Source code: 

/*

* this code is made by crazyacking

* Verdict: Accepted

* Submission Date: 2015-09-11-16.33

* Time: 0MS

* Memory: 137KB

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#define max(a,b) (a>b?a:b)

using

namespace

std;

typedef

long

long(

LL);

typedef

unsigned

long

long(

ULL);

const

double

eps(

1e-8);

const

int NN

=

100100;

int p

[NN

];

bool

v

[NN

];

int

num

=-

1;

void

makePrime()

{

     

int

i

,

j;

     

for(

i

=

2;

i

<NN;

++

i)

     

{

           

if(

!

v

[

i

])

{

p

[

++

num

]

=

i;

}

           

for(

j

=

0;

j

<=

num

&&

i

*p

[

j

]

<NN;

++

j)

           

{

                 

v

[

i

*p

[

j

]]

=

true;

                 

if(

i

%p

[

j

]

==

0)

{

break;

}

           

}

     

}

}

vector

<

int

>

ve;

int n;

int

main()

{

     

makePrime();

     

scanf(

"%d"

,

&n);

     

for(

int

i

=

0;

i

<

num;

++

i)

     

{

           

if(p

[

i

]

<=n)

           

{

                 

int

t

=p

[

i

];

                 

while(

t

<=n)

                 

{

                       

ve

.

push_back(

t);

                       

t

=

t

*p

[

i

];

                 

}

           

}

           

else

break;

     

}

     

int

si

=

ve

.

size();

     

printf(

"%d

\n

"

,

si);

     

for(

int

i

=

0;

i

<

si;

++

i)

           

printf(

i

==

si

-

1

?

"%d

\n

"

:

"%d "

,

ve

[

i

]);

     

return

0;

}

/*

*/