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. 	public static int[] smallestPrimeFact = new int[n + 1];
  12.  
  13. 	public static void smp(){
  14.  
  15. 	for(int i = 2; i <= n; i++){
  16. 			smallestPrimeFact[i] = i;
  17. 		}
  18.  
  19. 		for(int i = 2; i <= Math.sqrt(n); i++){
  20. 			if(smallestPrimeFact[i] == i){
  21. 				for(int j = i*i; j <= n; j += i){
  22. 					if(smallestPrimeFact[j] == j){
  23. 						smallestPrimeFact[j] = i; 
  24. 					}
  25. 				}
  26. 			}
  27. 		}
  28. 	}
  29.  
  30. 	public static HashMap<Integer, Integer> function(int vl){
  31. 		HashMap<Integer, Integer> map = new HashMap<>();
  32.  
  33. 		while(vl != 1){
  34. 			int d = smallestPrimeFact[vl];
  35. 			map.put(d, map.getOrDefault(d,0) + 1);
  36. 			vl /= d;
  37. 		}
  38. 		return map;
  39. 	}
  40.  
  41. 	public static void main (String[] args) throws java.lang.Exception
  42. 	{
  43. 		// your code goes here
  44. 		int N = 5;
  45. 		int[] arr = {1, 36, 9, 4, 6};
  46.  
  47. 		Long count = 0L;
  48.  
  49. 		smp();
  50.  
  51. 		HashMap<Long, Long> map = new HashMap<>();
  52.  
  53. 		for(int i = 0; i < N; i++){
  54. 			HashMap<Integer, Integer> k = function(arr[i]);
  55.  
  56. 			long g = 1;
  57.  
  58. 			for(Map.Entry<Integer, Integer> en : k.entrySet()){
  59. 				int key = en.getKey();
  60. 				int freq = en.getValue();
  61.  
  62. 				if(freq % 2 != 0){
  63. 					g *= key;
  64. 				}
  65. 			}
  66.  
  67. 			count += map.getOrDefault(g, 0L);
  68. 			map.put(g, map.getOrDefault(g, 0L) + 1);
  69. 		}
  70. 		System.out.println(count);
  71. 	}
  72. }
Success #stdin #stdout 0.09s 57092KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6
https://ideone.com/nPnNrd
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!