fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. /* Name of the class has to be "Main" only if the class is public. */
  6. class Ideone
  7. {
  8. 	public static int[] getPrime(int maxRange){
  9. 		boolean[] primes = new boolean[maxRange+1];
  10. 		int[] finalPrimes = new int[1229];
  11. 		primes[0]=primes[1]=true;
  12. 		for(int i=4;i<=maxRange;i+=2)
  13. 			primes[i]=true;
  14. 		for(int i=3;i*i<=maxRange;i+=2){
  15. 			for(int j=i*i;j<=maxRange;j+=i){
  16. 				primes[j]=true;
  17. 			}
  18. 		}
  19.  
  20. 		finalPrimes[0]=2;
  21. 		int i=0;
  22. 		for(int x=3; x<=maxRange; x+=2){
  23. 			if(!primes[x])
  24. 				finalPrimes[++i]=x;
  25. 		}
  26. 		return finalPrimes;
  27. 	}
  28.  
  29. 	public static int binarySearch(int[] a, int x){
  30. 		int low = 0, high=a.length-1;
  31. 		while(low<=high){
  32. 			int mid = low + (high-low)/2;
  33. 			if(a[mid] == x){
  34. 				return mid;
  35. 			}else if(x>a[mid]){
  36. 				low = mid+1;
  37. 			}else{
  38. 				high=mid-1;
  39. 			}
  40. 		}
  41. 		return low-1;
  42. 	}
  43.  
  44. 	public static HashMap<Integer, Integer> getFactors(int[] primes, int x){
  45. 		HashMap<Integer, Integer> hmap = new HashMap<>();
  46. 		if(x==1){
  47. 			return hmap;	
  48. 		}
  49. 		int index = binarySearch(primes, (int) Math.sqrt(x));
  50. 		while(x>1 && index >=0){
  51. 			if(x % primes[index] == 0){
  52. 				int count = 0;
  53. 				int temp = primes[index]*primes[index];
  54. 				while(x % temp == 0){
  55. 					x = x / temp;
  56. 					count+=2;
  57. 				}
  58. 				if(x% primes[index] == 0){
  59. 					x = x / primes[index];
  60. 					count+=1;
  61. 				}
  62. 				hmap.put(primes[index], count);
  63. 				// System.out.println(primes[index]+" "+count);
  64. 			}
  65. 			index--;
  66. 		}
  67. 		if(x!=1){
  68. 			hmap.put(x, 1);
  69. 			// System.out.println(x+" "+1);
  70. 		}
  71. 		return hmap;
  72. 	}
  73.  
  74. 	public static void main (String[] args) throws java.lang.Exception
  75. 	{
  76. 		// your code goes here
  77. 		int[] primes = getPrime(10000);
  78. 		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
  79.         int t = Integer.parseInt(input.readLine());
  80.         while(t-- > 0){
  81. 			String[] input1 = input.readLine().split(" ");
  82. 			String[] input2 = input.readLine().split(" ");
  83. 			int n = Integer.parseInt(input1[0]);
  84. 			int m = Integer.parseInt(input1[1]);
  85. 			int[] a = new int[n];
  86. 			for(int i=0;i<n;i++){
  87. 				a[i] = Integer.parseInt(input2[i]);
  88. 			}
  89. 			HashMap<Integer, Integer> lcm = new HashMap<>();
  90. 			for(int x : a){
  91. 				HashMap<Integer, Integer> factors = getFactors(primes, x);
  92. 				Iterator i = factors.entrySet().iterator();
  93. 				while(i.hasNext()){
  94. 					Map.Entry pair = (Map.Entry) i.next();
  95. 					int key = (int) pair.getKey(); //pair.getValue());
  96. 					int new_value = (int) pair.getValue();
  97. 					if(lcm.containsKey(key)){
  98. 						new_value = Math.max(new_value, (int) lcm.get(key));
  99. 					}
  100. 					lcm.put(key, new_value);
  101. 				}
  102. 			}
  103. 			int maxFold = 1, minValue=1;
  104. 			for(int j=2;j<=m;j++){
  105. 				int tempFold = 1; 
  106. 				HashMap<Integer, Integer> tempFactors = getFactors(primes, j);
  107. 				Iterator i = tempFactors.entrySet().iterator();
  108. 				while(i.hasNext()){
  109. 					Map.Entry pair = (Map.Entry) i.next();
  110. 					int key = (int) pair.getKey(); //pair.getValue());
  111. 					if(!lcm.containsKey(key)){
  112. 						tempFold*=(int) Math.pow(key, (int) pair.getValue());
  113. 					}else if(lcm.get(key)< (int) pair.getValue()){
  114. 						tempFold*=(int) Math.pow(key, ((int) pair.getValue() - lcm.get(key)));
  115. 					}
  116. 				}
  117. 				if(tempFold>maxFold){
  118. 					maxFold = tempFold;
  119. 					minValue = j;
  120. 				}
  121. 			}
  122. 			System.out.println(minValue);
  123.         }
  124. 	}
  125. }
Success #stdin #stdout 0.1s 32756KB
comments (?)
stdin
copy 
2
3 2
2 1 2
4 7
2 5 6 3
stdout
copy 
1
7
https://ideone.com/9yz2b5
language:
Java (HotSpot 12)
created:
4 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!