fork download
copy 
  1.  
  2. import java.util.*;
  3. import java.lang.*;
  4. import java.io.*;
  5. import java.math.*;
  6.  
  7. /*
  8.  * Coded by  	: Jaswant Singh [joney_000]
  9.  * Lang   		: Java
  10.  * Algorithm 	: Simple Math and Binary Search ,,Key Point : lib sqrt or pow have error at some precesion 
  11.  * Date         : 7/Sept/2015
  12.  */ 
  13. class Solution{	
  14.  
  15.     //Fast Reader implementation , handles large io files
  16.     private boolean finished = false;
  17.  
  18. 	private InputStream stream;
  19. 	private byte[] buf = new byte[1024];  //input Buffer
  20. 	private int curChar;
  21. 	private int numChars;
  22. 	private SpaceCharFilter filter;		  
  23.  
  24. 	public Solution(){
  25. 	     //The Default Constructor
  26. 		 //Place for some initialization work
  27. 	}
  28. 	public Solution(InputStream stream){
  29. 		this.stream = stream;
  30. 	}
  31.  
  32.     public static InputStream inputStream = System.in;
  33. 	public static OutputStream outputStream = System.out;
  34. 	public static Solution in = new Solution(inputStream);
  35.     public static PrintWriter out = new PrintWriter(outputStream);;
  36. 	/*
  37. 		Overhead [Additional Temporary Storage] 
  38. 		But it save a lot of time and Re Allocation of Space
  39. 		take care of Limit : 10^5 + 5 
  40. 	*/
  41. 	public static int tempints[] = new int[100005];
  42. 	public static long templongs[] = new long[100005];
  43. 	public static double tempdoubles[] = new double[100005];
  44. 	public static char tempchars[] = new char[100005];
  45. 	public static long mod = 1000000000+7;
  46.  
  47. 	public static void main(String[] args) throws java.lang.Exception{
  48. 		//let_me_start :) :D
  49.  
  50. 		int tests = i(); //int m = i();
  51.  
  52. 		 long ans=0;
  53. 		 for(int t=1;t<=tests;t++){
  54. 		   long P = l();long Q = l();
  55. 		   long left = sqrtLower(P);
  56. 		   long right = sqrtLower(Q);
  57. 		   ans = right-left;
  58. 		   if(left*left==P)ans=ans + 1;
  59. 		   out.write(""+ans+"\n");
  60. 		 }
  61.  
  62. 		out.flush();
  63. 		return;
  64.  
  65. 	}// END of PSVM	 
  66.  
  67.  
  68.  
  69.  public static long sqrtLower(long n)throws Exception{
  70. 	 long l = 1; long r = 2000000000L;
  71. 	  long mid=0;
  72. 	 while(l<=r){
  73. 		 mid = l + (r-l)/2;
  74. 		 if(mid*mid < n){
  75. 			 l = mid+1;
  76. 		 }else if(mid*mid==n){ 
  77. 			 return mid ;
  78. 		 }else{
  79. 			 r = mid-1;
  80. 		 }
  81. 	 }
  82. 	 return l-1;
  83.  }
  84.  
  85.  
  86. //                   My Utilities for Contest                //
  87.  
  88.  public static boolean isPrime(long n)throws Exception{
  89. 	if(n==1)return false;
  90. 	if(n<=3)return true;
  91. 	if(n%2==0)return false;
  92. 	for(int i=2 ;i <= Math.sqrt(n); i++){
  93. 		if(n%i==0)return false;
  94. 	}
  95. 	return true;
  96.  }
  97.  public static long gcd (long a , long b)throws Exception{
  98. 	if(b==0)return a;
  99. 	return gcd(b , a%b);
  100.  }
  101.  public static long lcm (long a , long b)throws Exception{
  102. 	if(a==0||b==0)return 0;
  103. 	return (a*b)/gcd(a,b);         //TAKE CARE OF Integer RANGE OVERFLOW
  104.  }
  105.  public static long mulmod(long a , long b ,long mod)throws Exception{
  106. 	if(a==0||b==0)return 0;
  107. 	if(b==1)return a;
  108. 	long ans = mulmod(a,b/2,mod);
  109. 	ans = (ans*2)% mod;
  110. 	if(b%2==1)ans = (a + ans)% mod;
  111. 	return ans;
  112.  }
  113.  public static long pow(long a , long b ,long mod)throws Exception{
  114. 	if(b==0)return 1;
  115. 	if(b==1)return a;
  116. 	long ans = pow(a,b/2,mod);
  117. 	ans = (ans * ans)% mod;
  118. 	if(b%2==1)ans = (a * ans)% mod;
  119. 	return ans;
  120.  }
  121.  // 20*20   nCr Pascal Table
  122.  public static long[][] ncrTable()throws Exception{
  123. 	long ncr[][] = new long[21][21];
  124. 	for(int i=0 ;i<=20 ;i++){ncr[i][0]=1;ncr[i][i]=1;}
  125. 	for(int j=0;j<=20 ;j++){
  126. 		for(int i=j+1;i<= 20 ;i++){
  127. 			ncr[i][j] = ncr[i-1][j]+ncr[i-1][j-1];
  128. 		}
  129. 	}
  130. 	return ncr;
  131.  }
  132. //							My I/O function                    	//
  133. public static int i()throws Exception{
  134.  return in.nextInt();                   					   //read a single Integer
  135. }
  136. public static int[] is(int n)throws Exception{               
  137.   for(int i=1 ; i <= n ;i++)tempints[i] = in.nextInt();        //read N integers
  138.  return tempints;
  139. }
  140. public static long l()throws Exception{                        //read a single Long
  141.  return in.nextLong();
  142. }
  143. public static long[] ls(int n)throws Exception{				   //read N Long type digits
  144.   for(int i=1 ; i <= n ;i++)templongs[i] = in.nextLong();  
  145.  return templongs;
  146. }
  147.  
  148. public static double d()throws Exception{
  149.   return in.nextDouble();
  150. }
  151. public static double[] ds(int n)throws Exception{
  152.   for(int i=1 ; i <= n ;i++)tempdoubles[i] = in.nextDouble();  
  153.  return tempdoubles;
  154. }
  155. public static char c()throws Exception{
  156.  return in.nextCharacter();
  157. }
  158. public static char[] cs(int n)throws Exception{
  159.   for(int i=1 ; i <= n ;i++)tempchars[i] = in.nextCharacter();  
  160.  return tempchars;
  161. }
  162. public static String s()throws Exception{
  163.  return in.nextLine();
  164. }
  165. public static BigInteger bi()throws Exception{
  166.  return in.nextBigInteger();
  167. }
  168.  
  169. //*********************** for 0.2%f [precision data]***********************//
  170.  /* 
  171.   * roundoff upto 2 digits 
  172.   * double roundOff = Math.round(a * 100.0) / 100.0;
  173.   *                  or
  174.   * System.out.printf("%.2f", val);
  175.   *				
  176.   */
  177. /*
  178.   *print upto 2 digits after decimal
  179.   *val = ((long)(val * 100.0))/100.0;
  180.   *
  181. */
  182.  
  183.  
  184. 	public int read(){
  185. 		if (numChars == -1){
  186. 			throw new InputMismatchException ();
  187. 		}
  188. 		if (curChar >= numChars){
  189. 			curChar = 0;
  190. 			try{
  191. 				numChars = stream.read (buf);
  192. 			} catch (IOException e){
  193. 				throw new InputMismatchException ();
  194. 			}
  195. 			if (numChars <= 0){
  196. 				return -1;
  197. 			}
  198. 		}
  199. 		return buf[curChar++];
  200. 	}
  201.  
  202. 	public int peek(){
  203. 		if (numChars == -1){
  204. 			return -1;
  205. 		}
  206. 		if (curChar >= numChars){
  207. 			curChar = 0;
  208. 			try{
  209. 				numChars = stream.read (buf);
  210. 			} catch (IOException e){
  211. 				return -1;
  212. 			}
  213. 			if (numChars <= 0){
  214. 				return -1;
  215. 			}
  216. 		}
  217. 		return buf[curChar];
  218. 	}
  219.  
  220. 	public int nextInt(){
  221. 		int c = read ();
  222. 		while (isSpaceChar (c))
  223. 			c = read ();
  224. 		int sgn = 1;
  225. 		if (c == '-'){
  226. 			sgn = -1;
  227. 			c = read ();
  228. 		}
  229. 		int res = 0;
  230. 		do{
  231. 			if(c==','){
  232. 				c = read();
  233. 			}
  234. 			if (c < '0' || c > '9'){
  235. 				throw new InputMismatchException ();
  236. 			}
  237. 			res *= 10;
  238. 			res += c - '0';
  239. 			c = read ();
  240. 		} while (!isSpaceChar (c));
  241. 		return res * sgn;
  242. 	}
  243.  
  244. 	public long nextLong(){
  245. 		int c = read ();
  246. 		while (isSpaceChar (c))
  247. 			c = read ();
  248. 		int sgn = 1;
  249. 		if (c == '-'){
  250. 			sgn = -1;
  251. 			c = read ();
  252. 		}
  253. 		long res = 0;
  254. 		do{
  255. 			if (c < '0' || c > '9'){
  256. 				throw new InputMismatchException ();
  257. 			}
  258. 			res *= 10;
  259. 			res += c - '0';
  260. 			c = read ();
  261. 		} while (!isSpaceChar (c));
  262. 		return res * sgn;
  263. 	}
  264.  
  265. 	public String nextString(){
  266. 		int c = read ();
  267. 		while (isSpaceChar (c))
  268. 			c = read ();
  269. 		StringBuilder res = new StringBuilder ();
  270. 		do{
  271. 			res.appendCodePoint (c);
  272. 			c = read ();
  273. 		} while (!isSpaceChar (c));
  274. 		return res.toString ();
  275. 	}
  276.  
  277. 	public boolean isSpaceChar(int c){
  278. 		if (filter != null){
  279. 			return filter.isSpaceChar (c);
  280. 		}
  281. 		return isWhitespace (c);
  282. 	}
  283.  
  284. 	public static boolean isWhitespace(int c){
  285. 		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  286. 	}
  287.  
  288. 	private String readLine0(){
  289. 		StringBuilder buf = new StringBuilder ();
  290. 		int c = read ();
  291. 		while (c != '\n' && c != -1){
  292. 			if (c != '\r'){
  293. 				buf.appendCodePoint (c);
  294. 			}
  295. 			c = read ();
  296. 		}
  297. 		return buf.toString ();
  298. 	}
  299.  
  300. 	public String nextLine(){
  301. 		String s = readLine0 ();
  302. 		while (s.trim ().length () == 0)
  303. 			s = readLine0 ();
  304. 		return s;
  305. 	}
  306.  
  307. 	public String nextLine(boolean ignoreEmptyLines){
  308. 		if (ignoreEmptyLines){
  309. 			return nextLine ();
  310. 		}else{
  311. 			return readLine0 ();
  312. 		}
  313. 	}
  314.  
  315. 	public BigInteger nextBigInteger(){
  316. 		try{
  317. 			return new BigInteger (nextString ());
  318. 		} catch (NumberFormatException e){
  319. 			throw new InputMismatchException ();
  320. 		}
  321. 	}
  322.  
  323. 	public char nextCharacter(){
  324. 		int c = read ();
  325. 		while (isSpaceChar (c))
  326. 			c = read ();
  327. 		return (char) c;
  328. 	}
  329.  
  330. 	public double nextDouble(){
  331. 		int c = read ();
  332. 		while (isSpaceChar (c))
  333. 			c = read ();
  334. 		int sgn = 1;
  335. 		if (c == '-'){
  336. 			sgn = -1;
  337. 			c = read ();
  338. 		}
  339. 		double res = 0;
  340. 		while (!isSpaceChar (c) && c != '.'){
  341. 			if (c == 'e' || c == 'E'){
  342. 				return res * Math.pow (10, nextInt ());
  343. 			}
  344. 			if (c < '0' || c > '9'){
  345. 				throw new InputMismatchException ();
  346. 			}
  347. 			res *= 10;
  348. 			res += c - '0';
  349. 			c = read ();
  350. 		}
  351. 		if (c == '.'){
  352. 			c = read ();
  353. 			double m = 1;
  354. 			while (!isSpaceChar (c)){
  355. 				if (c == 'e' || c == 'E'){
  356. 					return res * Math.pow (10, nextInt ());
  357. 				}
  358. 				if (c < '0' || c > '9'){
  359. 					throw new InputMismatchException ();
  360. 				}
  361. 				m /= 10;
  362. 				res += (c - '0') * m;
  363. 				c = read ();
  364. 			}
  365. 		}
  366. 		return res * sgn;
  367. 	}
  368.  
  369. 	public boolean isExhausted(){
  370. 		int value;
  371. 		while (isSpaceChar (value = peek ()) && value != -1)
  372. 			read ();
  373. 		return value == -1;
  374. 	}
  375.  
  376. 	public String next(){
  377. 		return nextString ();
  378. 	}
  379.  
  380. 	public SpaceCharFilter getFilter(){
  381. 		return filter;
  382. 	}
  383.  
  384. 	public void setFilter(SpaceCharFilter filter){
  385. 		this.filter = filter;
  386. 	}
  387.  
  388. 	public interface SpaceCharFilter{
  389. 		public boolean isSpaceChar(int ch);
  390. 	}
  391. }
  392.  
  393.  
  394.  
Success #stdin #stdout 0.13s 320576KB
comments (?)
stdin
copy 
2
1 3
1 5
stdout
copy 
1
2
https://ideone.com/GLITZL
language:
Java (12.0.1)
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!