fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Main {
  6. 	public static int findGCD(int x, int y) {
  7. 	    if (y == 0)
  8. 	        return x;
  9. 	    return findGCD(y, x % y);
  10. 	}
  11.  
  12. 	public static ArrayList<Integer> findGood(int[] blocks){
  13. 		int n = blocks.length;
  14. 		int j = 0;
  15. 		int cnt = 0;
  16. 		ArrayList<Integer> chains = new ArrayList<>();
  17. 		while(j<n){
  18. 			if(findGCD(blocks[j%n], blocks[(j+1)%n]) != 1){
  19. 				cnt++;
  20. 			}
  21. 			else{
  22. 				chains.add(cnt);
  23. 				cnt = 0;
  24. 			}
  25. 			j++;
  26. 		}
  27.  
  28. 		chains.add(cnt);
  29.  
  30. 		return chains;
  31. 	}
  32.  
  33. 	public static void main (String[] args) throws java.lang.Exception {
  34. 		Scanner sc = new Scanner(System.in);
  35. 		int n = sc.nextInt();
  36. 		int[] blocks = new int[n];
  37. 		int[] res = new int[n+1];
  38. 		int ins = 0;
  39. 		for(int i=0;i<n;i++){
  40. 			blocks[i] = sc.nextInt();
  41. 		}
  42.  
  43. 		ArrayList<Integer> chains = findGood(blocks);
  44.  
  45. 		for(int k=2;k<=n;k++){
  46. 			ins = 0;
  47. 			for(int chain: chains){
  48. 				ins += (chain/(k-1));
  49. 			}
  50. 			res[k] = ins;
  51. 		}
  52.  
  53. 		for(int k=2;k<=n;k++){
  54. 			System.out.print(res[k] + " ");
  55. 		}
  56. 	}
  57. }
Success #stdin #stdout 0.15s 59020KB
comments (?)
stdin
copy 
7
2 4 6 8 10 12 14
stdout
copy 
7 3 2 1 1 1
https://ideone.com/qIRe94
language:
Java (HotSpot 12)
created:
19 hours 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!