Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- public class Main
- {
- public static int max_size = 2 * (int)Math.pow(10,7) + 1;
- public static boolean[] dp = new boolean[max_size];
- public static int[] lastPrimeDivisor = new int[max_size];
- public static int[] numOfDivisors = new int[max_size];
- public static void main(String[] args) throws IOException
- {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- preprocess();
- int t = Integer.parseInt(br.readLine());
- while(t > 0)
- {
- int n = Integer.parseInt(br.readLine());
- if(dp[n] == true)
- System.out.println("Ada");
- else
- System.out.println("Vinit");
- t--;
- }
- }
- public static void markLastPrimeDivisor()
- {
- for(int i = 0 ; i < max_size ; i++)
- {
- lastPrimeDivisor[i] = 1;
- }
- for(int i = 2 ; i < max_size ; i += 2)
- {
- lastPrimeDivisor[i] = 2;
- }
- int o = (int)Math.sqrt(max_size) + 1;
- for(int i = 3 ; i < max_size; i++)
- {
- if(lastPrimeDivisor[i] != 1)
- {
- continue;
- }
- lastPrimeDivisor[i] = i;
- if(i <= o)
- {
- for(int j = i * i ; j < max_size ; j += 2 * i)
- {
- lastPrimeDivisor[j] = i;
- }
- }
- }
- /*for(int i = 1 ; i < max_size ; i++)
- System.out.println("last prime of " + i + " is " + lastPrimeDivisor[i]);*/
- }
- public static void countDivisors(int num)
- {
- int original = num;
- int result = 1;
- int currDivisorCount = 1;
- int currDivisor = lastPrimeDivisor[num];
- int nextDivisor;
- while(currDivisor != 1)
- {
- num = num / currDivisor;
- nextDivisor = lastPrimeDivisor[num];
- if(nextDivisor == currDivisor)
- {
- currDivisorCount++;
- }
- else
- {
- result = result * (currDivisorCount + 1);
- currDivisorCount = 1;
- currDivisor = nextDivisor;
- }
- }
- if(num != 1)
- {
- result = result * (currDivisorCount + 1);
- }
- //System.out.println("result for num : " + original + ", " + result);
- numOfDivisors[original] = result;
- }
- public static void countAllDivisors()
- {
- markLastPrimeDivisor();
- for(int i = 2 ; i < max_size ; i++)
- {
- countDivisors(i);
- //System.out.println("num of divisors of " + i + " = " + numOfDivisors[i]);
- }
- }
- public static void preprocess()
- {
- countAllDivisors();
- dp[0] = dp[1] = dp[2] = true;
- for(int i = 3 ; i < max_size ; i++)
- {
- int flag = 0;
- int limit = numOfDivisors[i];
- for(int j = 1 ; j <= limit; j++)
- {
- //If for any i - j, we get false,for playing optimally
- //the current opponent will choose to take j stones out of the
- //pile as for i - j stones, the other player is not winning.
- if(dp[i - j] == false)
- {
- dp[i] = true;
- flag = 1;
- break;
- }
- }
- if(flag == 0)
- dp[i] = false;
- }
- }
- }
Add Comment
Please, Sign In to add comment