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.  static int gcd(int a, int b) {
  11.         while (b != 0) {
  12.             int temp = b;
  13.             b = a % b;
  14.             a = temp;
  15.         }
  16.         return a;
  17.     }
  18.  
  19.     public static void main(String[] args) {
  20.  
  21.         int[] arr = {5, 12, 8, 21, 3, 17, 9, 14, 6, 25};
  22.         int n = arr.length;
  23.  
  24.         List<Integer> chainSizes = new ArrayList<>();
  25.  
  26.         boolean[] visited = new boolean[n];
  27.  
  28.         for (int start = 0; start < n; start++) {
  29.  
  30.             if (visited[start]) continue;
  31.  
  32.             int size = 1;
  33.             visited[start] = true;
  34.  
  35.             int current = start;
  36.  
  37.             while (true) {
  38.                 int next = (current + 1) % n;
  39.  
  40.                 if (visited[next]) break;
  41.  
  42.                 if (gcd(arr[current], arr[next]) > 1) {
  43.                     size++;
  44.                     visited[next] = true;
  45.                     current = next;
  46.                 } else {
  47.                     break;
  48.                 }
  49.             }
  50.  
  51.             if (size > 1) {
  52.                 chainSizes.add(size);
  53.             }
  54.         }
  55.  
  56.        int[] chains = new int[n];
  57.  
  58.        for(int i : chainSizes){
  59.        	chains[i]++;
  60.        }
  61.  
  62.        int[] preSum = new int[chains.length + 3];
  63.        preSum[0] = chains[0];
  64.  
  65.        for(int i = 1 ; i < chains.length; i++){
  66.        	preSum[i] = preSum[i-1] + chains[i];
  67.        }
  68.  
  69.        int sum = 0;
  70.  
  71.        for(int i = 1; i < chains.length; i++){
  72.        	int ansi = 0;
  73.        	int g = 1;
  74.        	for(int l = i; l + i - 1 < chains.length; l+=i){
  75.        	int range = preSum[l + i - 1] - (l > 0 ? preSum[l - 1] : 0);
  76.         ansi += g * range;
  77.         g++;
  78.        	}
  79.        	sum += ansi;
  80.        }
  81.  
  82.        System.out.print(sum);
  83. 	}
  84. }
Success #stdin #stdout 0.07s 52456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9
https://ideone.com/aKIi5j
language:
Java (HotSpot 12)
created:
6 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!