Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.File;
- import java.io.FileReader;
- import java.io.IOException;
- import java.io.PrintWriter;
- import java.io.StreamTokenizer;
- import java.util.Arrays;
- public class Main {
- public static void main(String[] args) throws IOException {
- StreamTokenizer in = new StreamTokenizer(new BufferedReader(new FileReader("gcdarray.in")));
- PrintWriter pw = new PrintWriter(new File("gcdarray.out"));
- in.nextToken();
- int t = (int)in.nval;
- for(int k = 1; k <= t; k++) {
- in.nextToken();
- int n = (int)in.nval;
- int arr[] = new int[n+1];
- int cntEven = 0;
- for(int i = 1; i <= n; i++) {
- in.nextToken();
- arr[i] = (int)in.nval;
- if(arr[i] % 2 == 0) cntEven++;
- }
- arr[0] = arr[1];
- if(cntEven == n) {
- int cnt = 0;
- for(int i = 1; i <= n; i++) {
- if(arr[i] < arr[i-1]) {
- cnt += arr[i-1]-arr[i];
- arr[i] += arr[i-1]-arr[i];
- }
- }
- pw.println(cnt);
- continue;
- } else {
- boolean prime[] = new boolean[20001];
- Arrays.fill(prime, true);
- prime[0] = prime[1] = false;
- for(int i = 2; i <= Math.sqrt(1.0 * 20000); i++) {
- if(prime[i]) {
- for(int j = i*i; j <= 20000; j+=i) {
- prime[j] = false;
- }
- }
- }
- int min = Integer.MAX_VALUE;
- for(int x = 2; x <= 10000; x++) {
- if(prime[x]) {
- int mas[] = new int[n+1];
- int cnt = 0;
- System.arraycopy(arr, 0, mas, 0, arr.length);
- for(int i = 1; i <= n; i++) {
- if(mas[i] < mas[i-1]) {
- cnt += mas[i-1]-mas[i];
- mas[i] += mas[i-1]-mas[i];
- }
- while(mas[i] % x != 0) {
- cnt++;
- mas[i]++;
- }
- }
- if(cnt < min) min = cnt;
- }
- }
- pw.println(min);
- continue;
- }
- }
- pw.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement