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