數學 - Codeforces Round #319 (Div. 1)A. Vasya and Petya's GameVasya and Petya's Game Problem's Link

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;