You are viewing a single comment's thread. Return to all comments →
simple and easy solution
using namespace std; const int N = 200100; const int M = 100100; bool unprime[N]; int prime[N], primecnt[M]; int n, num;
void init(){ num = 0; memset(unprime, 0, sizeof(unprime)); memset(primecnt, 0, sizeof(primecnt)); for(int i = 2 ; i < N ; ++ i){ if(!unprime[i]) prime[num ++]=i; for(int j = 0 ; j < num && i * prime[j] < N ; ++ j) { unprime[i*prime[j]] = 1; if(!(i % prime[j] )) break; } } int id = 0; for(int i = 2; i < M; ++ i){ primecnt[i] = primecnt[i - 1]; if(i == prime[id]){ ++ primecnt[i]; ++ id; } } }
int main(){ init(); int T; scanf("%d",&T); while(T --){ scanf("%d",&n); if(primecnt[n]%2 == 1) puts("Alice"); else puts("Bob"); } return 0; }
Seems like cookies are disabled on this browser, please enable them to open this website
Alice and Bob's Silly Game
You are viewing a single comment's thread. Return to all comments →
simple and easy solution
using namespace std; const int N = 200100; const int M = 100100; bool unprime[N]; int prime[N], primecnt[M]; int n, num;
void init(){ num = 0; memset(unprime, 0, sizeof(unprime)); memset(primecnt, 0, sizeof(primecnt)); for(int i = 2 ; i < N ; ++ i){ if(!unprime[i])
prime[num ++]=i;
for(int j = 0 ; j < num && i * prime[j] < N ; ++ j) {
unprime[i*prime[j]] = 1;
if(!(i % prime[j] ))
break;
}
} int id = 0; for(int i = 2; i < M; ++ i){ primecnt[i] = primecnt[i - 1]; if(i == prime[id]){ ++ primecnt[i]; ++ id; } } }
int main(){ init(); int T; scanf("%d",&T); while(T --){ scanf("%d",&n); if(primecnt[n]%2 == 1) puts("Alice"); else puts("Bob"); } return 0; }