Advertisement
Guest User

Untitled

a guest
Jan 28th, 2020
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.79 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.File;
  3. import java.io.FileReader;
  4. import java.io.IOException;
  5. import java.io.PrintWriter;
  6. import java.io.StreamTokenizer;
  7. import java.util.Arrays;
  8.  
  9.  
  10. public class Main {
  11. public static void main(String[] args) throws IOException {
  12. StreamTokenizer in = new StreamTokenizer(new BufferedReader(new FileReader("gcdarray.in")));
  13. PrintWriter pw = new PrintWriter(new File("gcdarray.out"));
  14. in.nextToken();
  15. int t = (int)in.nval;
  16. for(int k = 1; k <= t; k++) {
  17. in.nextToken();
  18. int n = (int)in.nval;
  19. int arr[] = new int[n+1];
  20. int cntEven = 0;
  21. for(int i = 1; i <= n; i++) {
  22. in.nextToken();
  23. arr[i] = (int)in.nval;
  24. if(arr[i] % 2 == 0) cntEven++;
  25. }
  26. arr[0] = arr[1];
  27. if(cntEven == n) {
  28. int cnt = 0;
  29. for(int i = 1; i <= n; i++) {
  30. if(arr[i] < arr[i-1]) {
  31. cnt += arr[i-1]-arr[i];
  32. arr[i] += arr[i-1]-arr[i];
  33. }
  34. }
  35. pw.println(cnt);
  36. continue;
  37. } else {
  38. boolean prime[] = new boolean[20001];
  39. Arrays.fill(prime, true);
  40. prime[0] = prime[1] = false;
  41. for(int i = 2; i <= Math.sqrt(1.0 * 20000); i++) {
  42. if(prime[i]) {
  43. for(int j = i*i; j <= 20000; j+=i) {
  44. prime[j] = false;
  45. }
  46. }
  47. }
  48. int min = Integer.MAX_VALUE;
  49. for(int x = 2; x <= 10000; x++) {
  50. if(prime[x]) {
  51. int mas[] = new int[n+1];
  52. int cnt = 0;
  53. System.arraycopy(arr, 0, mas, 0, arr.length);
  54. for(int i = 1; i <= n; i++) {
  55. if(mas[i] < mas[i-1]) {
  56. cnt += mas[i-1]-mas[i];
  57. mas[i] += mas[i-1]-mas[i];
  58. }
  59. while(mas[i] % x != 0) {
  60. cnt++;
  61. mas[i]++;
  62. }
  63. }
  64. if(cnt < min) min = cnt;
  65. }
  66. }
  67. pw.println(min);
  68. continue;
  69. }
  70. }
  71. pw.close();
  72. }
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement