Guest User

Untitled

a guest
Apr 8th, 2017
133
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.FileReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.util.ArrayList;
  6. import java.util.Arrays;
  7. import java.util.TreeSet;
  8.  
  9. class MonkAndAtm {
  10.     static final int MAX=10000001;
  11.  
  12.     static int factors[]=new int[MAX];
  13.  
  14.     public static void main(String[] args) throws IOException {
  15.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  16.         int t,n;
  17.         t=Integer.parseInt(br.readLine());
  18.         initFactors();
  19.  
  20.         StringBuilder sbr=new StringBuilder();
  21.         while (t-- > 0) {
  22.             n=Integer.parseInt(br.readLine());
  23.             sbr.append(solve(n)+"\n");
  24.             //System.out.println(solve(n));
  25.         }
  26.         System.out.print(sbr.toString());
  27.  
  28.     }
  29.  
  30.     private static int solve(int n) {
  31.  
  32.        
  33.         for (int m = n; m>0 ; m--) {
  34.             if (n%m==0)
  35.             {
  36.                 int temp=countFactors(m);
  37.                 if (isPowerOf2(temp))
  38.                     return temp;
  39.             }
  40.         }
  41.  
  42.         return 0;
  43.     }
  44.  
  45.     private static int countFactors(int n) {
  46.         int m=n,count=0,ans=1;
  47.         while (n>1){
  48.             count=0;
  49.             int x=factors[n];
  50.             while (n%x==0){
  51.                 count++;
  52.                 n/=x;
  53.             }
  54.             ans*=(count+1);
  55.         }
  56.         return ans;
  57.     }
  58.  
  59.  
  60.     public static boolean isPowerOf2(int n) {
  61.         if (n==1)
  62.             return true;
  63.  
  64.         if ((n&1)==1 || n==0)
  65.             return false;
  66.  
  67.         return isPowerOf2(n >> 1);
  68.     }
  69.  
  70.     private static void initFactors() {
  71.  
  72.         for (int i = 2; i < MAX; i+=2) {
  73.             factors[i]=2;
  74.         }
  75.  
  76.         int sqrt= (int) Math.sqrt(MAX);
  77.  
  78.         for (int i = 3; i <MAX; i+=2) {
  79.  
  80.             if (factors[i]==0){
  81.                 factors[i]=i;
  82.  
  83.                 for (int j =i*i; j>0 && j <MAX ; j+=2*i) {
  84.                     if (factors[j]==0)
  85.                         factors[j]=i;
  86.                 }
  87.             }
  88.         }
  89.  
  90.     }
  91. }
RAW Paste Data