fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6. 	private static int[] st;
  7.  
  8. 	public static void main(String[] args)throws IOException{
  9. 		PrintWriter pw = new PrintWriter(System.out);
  10.         InputReader in = new InputReader(System.in);
  11.         int n = in.nextInt();
  12.         int k = in.nextInt();
  13.         int[] a = new int[n+1];
  14.         boolean found = false;
  15.         boolean fnd = false;
  16.         for(int i=1;i<=n;i++){
  17.         	a[i] = in.nextInt();
  18.         	if(a[i]%k==0){
  19.         		if(a[i]==k){
  20.         			fnd = true;
  21.         		}
  22.         		found = true;
  23.         	}
  24.         }
  25.  
  26.         if(fnd ==true){
  27.         	pw.println("1");
  28.         }
  29.  
  30.         else if(found==false){
  31.         	pw.println("-1");
  32.         }
  33.  
  34.         else{
  35.         	constructSegmentTree(a);
  36.         	int min = 1000000009;
  37.         	 for(int i=1;i<n;i++){
  38.         		 if(a[i]%k!=0){
  39.         			 continue;
  40.         		 }
  41.         		 int low = i+1;
  42.         		 int high = n;
  43.         		 int mid = 0;
  44.         		 int note = 0;
  45.         		 while(true){
  46.         			 mid = low + (high-low)/2;
  47.         			 if(findRangeGcd(i, mid, a)>k){
  48.         				 low = mid;
  49.         			 }
  50.  
  51.         			 else if(findRangeGcd(i, mid, a)==k){
  52.         				 high = mid;
  53.         				 note = mid;
  54.         				 break;
  55.         			 }
  56.  
  57.         			 else{
  58.         				 high = mid;
  59.         			 }
  60.  
  61.         			 if(Math.abs(high-low)<=1){
  62.         				 if(findRangeGcd(i, low, a)==k){
  63.         					 note = low;
  64.         					 break;
  65.         				 }
  66.  
  67.         				 else if(findRangeGcd(i, high, a)==k){
  68.         					 note = high;
  69.         					 break;
  70.         				 }
  71.  
  72.         				 else{
  73.         					 break;
  74.         				 }
  75.         			 }
  76.         		 }
  77.  
  78.         		 if(note!=0){
  79.         			 min = Math.min(min, note - i + 1);
  80.         		 }
  81.         	 }
  82.         	 if(min == 1000000009)
  83.                  pw.println("-1");
  84.             else
  85.         	   pw.println(min);	 
  86.         }
  87.         pw.close();
  88. 	}
  89.  
  90. 	public static int[] constructSegmentTree(int[] arr){
  91.         int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
  92.         int size = 2*(int)Math.pow(2, height)-1; 
  93.         st = new int[size];
  94.         constructST(arr, 0, arr.length-1, 0);
  95.         return st;
  96.     }
  97.  
  98.     public static int constructST(int[] arr, int ss, int se, int si){
  99.         if(ss==se){
  100.             st[si] = arr[ss];
  101.             return st[si];
  102.         }
  103.         int mid = ss+(se-ss)/2;
  104.         st[si] = gcd(constructST(arr, ss, mid, si*2+1),constructST(arr, mid+1, se, si*2+2));
  105.         return st[si];
  106.     }
  107.  
  108.     private static int gcd(int a, int b) {
  109.  
  110.     	if(a<b){
  111.     		int c = b;
  112.     		b=a;
  113.     		a=c;
  114.     	}
  115. 		if(b==0){
  116. 			return a;
  117. 		}
  118.  
  119. 		if(b==1)
  120. 			return 1;
  121.  
  122. 		return gcd(b,a%b);
  123. 	}
  124.  
  125. 	//Finding The gcd of given Range
  126.     public static int findRangeGcd(int ss, int se, int[] arr){
  127.         int n = arr.length;
  128.         if(ss<0 || se > n-1 || ss>se){
  129.             throw new IllegalArgumentException("Invalid arguments");
  130.         }
  131.         return findGcd(0, n-1, ss, se, 0);
  132.     }
  133.  
  134.     public static int findGcd(int ss, int se, int qs, int qe, int si){ 
  135.         if(ss>qe || se < qs)return 0;
  136.         if(qs<=ss && qe>=se)return st[si];
  137.  
  138.         int mid = ss+(se-ss)/2;
  139.         return gcd(findGcd(ss, mid, qs, qe, si*2+1),findGcd(mid+1, se, qs, qe, si*2+2));
  140.     }
  141.  
  142. static class InputReader {
  143.  
  144. 		private InputStream stream;
  145. 		private byte[] buf = new byte[8192];
  146. 		private int curChar;
  147. 		private int snumChars;
  148. 		private SpaceCharFilter filter;
  149.  
  150. 		public InputReader(InputStream stream) {
  151. 			this.stream = stream;
  152. 		}
  153.  
  154. 		public int snext() {
  155. 			if (snumChars == -1)
  156. 				throw new InputMismatchException();
  157. 			if (curChar >= snumChars) {
  158. 				curChar = 0;
  159. 				try {
  160. 					snumChars = stream.read(buf);
  161. 				} catch (IOException e) {
  162. 					throw new InputMismatchException();
  163. 				}
  164. 				if (snumChars <= 0)
  165. 					return -1;
  166. 			}
  167. 			return buf[curChar++];
  168. 		}
  169.  
  170. 		public int nextInt() {
  171. 			int c = snext();
  172. 			while (isSpaceChar(c))
  173. 				c = snext();
  174. 			int sgn = 1;
  175. 			if (c == '-') {
  176. 				sgn = -1;
  177. 				c = snext();
  178. 			}
  179.  
  180. 			int res = 0;
  181.  
  182. 			do {
  183. 				if (c < '0' || c > '9')
  184. 					throw new InputMismatchException();
  185. 				res *= 10;
  186. 				res += c - '0';
  187. 				c = snext();
  188. 			} while (!isSpaceChar(c));
  189.  
  190. 			return res * sgn;
  191. 		}
  192.  
  193. 		public long nextLong() {
  194. 			int c = snext();
  195. 			while (isSpaceChar(c))
  196. 				c = snext();
  197. 			int sgn = 1;
  198. 			if (c == '-') {
  199. 				sgn = -1;
  200. 				c = snext();
  201. 			}
  202.  
  203. 			long res = 0;
  204.  
  205. 			do {
  206. 				if (c < '0' || c > '9')
  207. 					throw new InputMismatchException();
  208. 				res *= 10;
  209. 				res += c - '0';
  210. 				c = snext();
  211. 			} while (!isSpaceChar(c));
  212.  
  213. 			return res * sgn;
  214. 		}
  215.  
  216. 		public String readString() {
  217. 			int c = snext();
  218. 			while (isSpaceChar(c))
  219. 				c = snext();
  220. 			StringBuilder res = new StringBuilder();
  221. 			do {
  222. 				res.appendCodePoint(c);
  223. 				c = snext();
  224. 			} while (!isSpaceChar(c));
  225. 			return res.toString();
  226. 		}
  227.  
  228. 		public boolean isSpaceChar(int c) {
  229. 			if (filter != null)
  230. 				return filter.isSpaceChar(c);
  231. 			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  232. 		}
  233.  
  234. 		public interface SpaceCharFilter {
  235. 			public boolean isSpaceChar(int ch);
  236. 		}
  237. 	}
  238. }
  239.  
Success #stdin #stdout 0.09s 320576KB
comments (?)
stdin
copy 
4 3
5 6 9 7 10
stdout
copy 
2
https://ideone.com/wqVgEI
language:
Java (HotSpot 12)
created:
8 years 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!