fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static int n = (int)1e6;
  11.  
  12. 	public static int[] smallestPrimeFact = new int[n + 1];
  13.  
  14. 	public static HashMap<Integer, Integer> function(int vl){
  15. 		HashMap<Integer, Integer> map = new HashMap<>();
  16.  
  17. 		while(vl != 1){
  18. 			int d = smallestPrimeFact[vl];
  19. 			map.put(d, map.getOrDefault(d,0) + 1);
  20. 			vl /= d;
  21. 		}
  22. 		return map;
  23. 	}
  24.  
  25. 	public static void main (String[] args) throws java.lang.Exception
  26. 	{
  27. 		// your code goes here
  28. 		int N = 5;
  29. 		int[] arr = {1, 36, 9, 4, 6};
  30.  
  31. 		Long count = 0L;
  32.  
  33. 		for(int i = 2; i <= n; i++){
  34. 			smallestPrimeFact[i] = i;
  35. 		}
  36.  
  37. 		for(int i = 2; i <= Math.sqrt(n); i++){
  38. 			if(smallestPrimeFact[i] == i){
  39. 				for(int j = i*i; j <= n; j += i){
  40. 					if(smallestPrimeFact[j] == j){
  41. 						smallestPrimeFact[j] = i; 
  42. 					}
  43. 				}
  44. 			}
  45. 		}
  46.  
  47. 		HashMap<Long, Long> map = new HashMap<>();
  48.  
  49. 		for(int i = 0; i < N; i++){
  50. 			HashMap<Integer, Integer> k = function(arr[i]);
  51.  
  52. 			long g = 1;
  53.  
  54. 			for(Map.Entry<Integer, Integer> en : k.entrySet()){
  55. 				int key = en.getKey();
  56. 				int freq = en.getValue();
  57.  
  58. 				if(freq % 2 != 0){
  59. 					g *= key;
  60. 				}
  61. 			}
  62.  
  63. 			count += map.getOrDefault(g, 0L);
  64. 			map.put(g, map.getOrDefault(g, 0L) + 1);
  65. 		}
  66. 		System.out.println(count);
  67. 	}
  68. }
Success #stdin #stdout 0.09s 59140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6
https://ideone.com/FkEutp
language:
Java (HotSpot 12)
created:
1 day 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!