G. The jar of divisors
time limit per test:2 seconds
memory limit per test:64 megabytes
input:standard input
output:standard output
Alice and Bob play the following game. They choose a number N to play with. The rules are as follows:
– They write each number from 1 to N on a paper and put all these papers in a jar.
– Alice plays first, and the two players alternate.
– In his/her turn, a player can select any available number M and remove its divisors including M.
– The person who cannot make a move in his/her turn wins the game.
Assuming both players play optimally, you are asked the following question: who wins the game?
Input
The first line contains The number of test cases T (1 ≤ T ≤ 20). Each of The next T lines contains an INTEGER (1 ≤ N 1000000000) or less.
Output
Output T lines, one for each test case, containing Alice if Alice wins the game, or Bob otherwise.
Examples
Input
2
5
1
Copy the codeOutput
Alice
Bob
Copy the codeTitle links: codeforces.com/gym/100952/…
Each time A and B say an arbitrary number M, they will take away all the factors of M in the container. If the container is empty, they will lose
Ideas: Only 1 is a subsequent party win, because 1 only take time, greater than 1, assume that a and b are not smart, assuming that stones out of the x, y, for the cause as a result, a subsequent party win, now a and b are intelligent, Julio cruz can direct x * y (namely can copy the successful operation and Julio cruz, stones can include the cause of operation), then you can win the cause, So anything greater than 1 must be first hand!
Here is the AC code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 inline int read() 4 { 5 int x=0,f=1; 6 char ch=getchar(); 7 while(ch<'0'||ch>'9') 8 { 9 if(ch=='-') 10 f=-1; 11 ch=getchar(); 12 } 13 while(ch>='0'&&ch<='9') 14 { 15 x=x*10+ch-'0'; 16 ch=getchar(); 17 } 18 return x*f; 19 } 20 inline void write(int x) 21 { 22 if(x<0) 23 { 24 putchar('-'); 25 x=-x; 26 } 27 if(x>9) 28 write(x/10); 29 putchar(x%10+'0'); 30 } 31 int main() 32 { 33 int T; 34 T=read(); 35 while(T--) 36 { 37 int n; 38 n=read(); 39 if(n>1) 40 printf("Alice\n"); 41 else printf("Bob\n"); 42 } 43 return 0; 44}Copy the code