Vasya 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;
}
/*
*/
* 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;
}
/*
*/
