fork download
copy 
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. public class EvenNumberOfDivisors {
  6.  
  7. 	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  8. 	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  9. 	static StringTokenizer st = new StringTokenizer("");
  10.  
  11. 	public static String next() {
  12. 		try	{
  13. 		while (!st.hasMoreTokens()) {
  14. 			String s = br.readLine();
  15. 			if (s == null)
  16. 				return null;
  17. 			st = new StringTokenizer(s);
  18. 		}
  19. 		return st.nextToken();
  20. 		}	catch(Exception e)	{
  21. 			return	null;
  22. 		}
  23. 	}
  24. 	public static void main(String[] asda) throws Exception {
  25. 		long max = 10000000000000000L + 5;
  26. 		long [] squares = new long [ 1 + (int)(Math.sqrt(max)) ];
  27. 		for (long k = 1; k*k <= max; k++)	{
  28. 			squares[(int)(k-1)] = k*k;
  29. 		}
  30.  
  31. 		while	(true)	{
  32. 			long N = Long.parseLong( next() );
  33. 			long M = Long.parseLong( next() );
  34.  
  35. 			if (N == 0 && M == 0) {
  36. 				break;
  37. 			}
  38.  
  39. 			long size = M - N + 1;
  40. 			long x = f(squares, N, M);
  41. 			long ans = size - x;
  42. 			out.println(ans);
  43. 		}
  44.         //
  45.         out.flush();
  46.         System.exit(0);
  47.     }
  48.  
  49.     // nuumber of values in range [L, R] where the value has odd number of divisor (perfect square)
  50.     static int f(long [] squares, long L, long R)	{
  51.     	int low = firstHigheer(squares, L);
  52.     	int high = firstLower(squares, R);
  53.     //	out.printf("f(%d, %d) = %d - %d\n", L, R, low, high );
  54.     	return	high - low + 1;
  55.     }
  56.  
  57.  
  58.     // the first index with value >= key
  59. 	static int firstHigheer(long [] list, long key)	{
  60. 		int lo = 0, hi = list.length - 1;
  61. 		int ans = -1;
  62. 		while	( lo <= hi )	{
  63. 			int mid = (lo + hi) >> 1;
  64. 			if	( list[mid] >= key )	{
  65. 				ans = mid;	hi = mid - 1;
  66. 			}	else	lo = mid + 1;
  67. 		}
  68. 		return	ans;
  69. 	}
  70.  
  71. 	// the last index with value <= key
  72. 	static int firstLower(long [] list, long key)	{
  73. 		int lo = 0, hi = list.length - 1;
  74. 		int ans = -1;
  75. 		while	( lo <= hi )	{
  76. 			int mid = (lo + hi) >> 1;
  77. 			if	( list[mid] <= key )	{
  78. 				ans = mid;	lo = mid + 1;
  79. 			}	else	hi = mid - 1;
  80. 		}
  81. 		return	ans;
  82. 	}
  83.  
  84. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:5: error: class EvenNumberOfDivisors is public, should be declared in a file named EvenNumberOfDivisors.java
public class EvenNumberOfDivisors {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/Y6PZTV
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

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!