fork(1) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.FileReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5.  
  6. /**
  7.  * Created by hardCode on 4/8/2017.
  8.  */
  9. class MonkAndAtm {
  10.     static final int MAX=10000001;
  11.  
  12.     static int smallestFacctor[]=new int[MAX];
  13.  
  14.     public static void main(String[] args) throws IOException {
  15.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  16.         //BufferedReader br=new BufferedReader(new FileReader("input.txt"));
  17.         int t,n;
  18.  
  19.         t=Integer.parseInt(br.readLine());
  20.         initFactors();
  21.  
  22.         StringBuilder sbr=new StringBuilder();
  23.         while (t-- > 0) {
  24.  
  25.             n=Integer.parseInt(br.readLine());
  26.             //System.out.println("stuck at "+n);
  27.             sbr.append(solve(n) + "\n");
  28.             //System.out.println(solve(n));
  29.         }
  30.         System.out.print(sbr.toString());
  31.  
  32.  
  33.     }
  34.  
  35.     private static int solve(int n) {
  36.  
  37.         int sqrt= (int) Math.sqrt(n);
  38.  
  39.         int ans=Integer.MIN_VALUE;
  40.         for (int m =1; m<=sqrt ; m++) {
  41.             if (n%m==0)
  42.             {
  43.                 int x=n/m;
  44.                 //System.out.println(smallestFacctor[x]);
  45.                 int temp=countFactors(x);
  46.  
  47.                 if (isPowerOf2(temp))
  48.                     ans=Integer.max(temp,ans);
  49.  
  50.                 temp=countFactors(m);
  51.                 if (isPowerOf2(temp))
  52.                     ans=Integer.max(temp,ans);
  53.             }
  54.         }
  55.  
  56.         return ans;
  57.     }
  58.  
  59.     public static int countFactors(int n) {
  60.         int m=n,count=0,ans=1;
  61.  
  62.         while (n>1){
  63.             count=0;
  64.             int x= smallestFacctor[n];
  65.             //System.out.println(n+" "+x+" "+(n%x==0));
  66.             //System.out.println("s factor "+n+" "+x);
  67.             while (n%x==0){
  68.                 count++;
  69.                 n/=x;
  70.             }
  71.             ans*=(count+1);
  72.         }
  73.         return ans;
  74.     }
  75.  
  76.  
  77.     public static boolean isPowerOf2(int n) {
  78.         if (n==1)
  79.             return true;
  80.  
  81.         if ((n&1)==1 || n==0)
  82.             return false;
  83.  
  84.         return isPowerOf2(n >> 1);
  85.     }
  86.  
  87.     private static void initFactors() {
  88.  
  89.         for (int i = 2; i < MAX; i+=2) {
  90.             smallestFacctor[i]=2;
  91.         }
  92.         smallestFacctor[0]=1;
  93.         smallestFacctor[1]=1;
  94.  
  95.         int sqrt= (int) Math.sqrt(MAX);
  96.  
  97.         for (int i = 3; i <MAX; i+=2) {
  98.  
  99.             if (smallestFacctor[i]==0){
  100.  
  101.                 smallestFacctor[i]=i;
  102.  
  103.                 if ((long)i*i<MAX)
  104.                 for (int j =i*i; j <MAX ; j+=2*i) {
  105.                     if (smallestFacctor[j]==0)
  106.                         smallestFacctor[j]=i;
  107.                 }
  108.             }
  109.         }
  110.  
  111.     }
  112. }
  113.  
Success #stdin #stdout 0.14s 4386816KB
comments (?)
stdin
copy 
3
15
48
60
stdout
copy 
4
8
8
https://ideone.com/SCF7NM
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!