fork download
copy 
  1.  
  2.  
  3.  
  4.  
  5. 			import java.io.*;
  6. 			import java.util.*;
  7. 			class COMDIV
  8. 			{
  9. 				private static Reader in;
  10. 				private static PrintWriter out;
  11.  
  12. 				public static void main(String args[])
  13. 				throws IOException
  14. 				{
  15. 					in=new Reader();
  16. 					out=new PrintWriter(System.out,true);
  17.  
  18. 					BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  19. 					int t=Integer.parseInt(br.readLine());
  20. 					boolean isPrime[]=new boolean[1000+4];
  21. 					int primes[]=new int[1000+4];//this will store the nth prime. in consecutive order
  22. 					int p_idx=0;
  23.  
  24. 					Arrays.fill(isPrime, true);//initially assume that all are prime
  25. 					isPrime[0]=isPrime[1]=false;
  26.  
  27. 					for(int i=2;i*i<=1002;i++)
  28. 					{
  29. 						if(isPrime[i])
  30. 						{
  31. 							primes[p_idx++]=i;
  32. 							for(int j=i;i*j<=1002;j++)
  33. 								isPrime[i*j]=false;
  34. 						}
  35. 					}
  36.  
  37.  
  38. 					while(t--!=0) 
  39. 					{
  40. 						String in[]=br.readLine().split(" ");
  41. 						int a=Integer.parseInt(in[0]);
  42. 						int b=Integer.parseInt(in[1]);
  43. 						int g=gcd(a,b);
  44. 						if(g==1)
  45. 						{
  46. 							System.out.println(1);
  47. 							continue;
  48. 						}
  49. 						else
  50. 						{
  51. 							//all divisors of g and (common divisors of both (A&B)) are the same. its the same list
  52. 							//therefore the required no of divisors common to both a and b are the number of divisors of g.
  53. 							long prod=1;
  54. 							int i=0;
  55. 							while(primes[i]*primes[i]<=g) 	// && i<p_idx++
  56. 							{
  57. 								if(isPrime[primes[i]])
  58. 								{
  59. 									int c=0;
  60. 									while(g%primes[i]==0)
  61. 									{
  62.  
  63. 										g/=primes[i];
  64. 										c++;
  65. 									}
  66. 									prod=prod*(++c);
  67. 								}
  68. 								i++;
  69. 							}
  70. 							if(g>1)
  71. 								prod<<=1;
  72. 							System.out.println(prod);
  73. 						}
  74.  
  75. 					}//t
  76.  
  77. 					out.flush();
  78. 					out.close();
  79. 				}
  80.  
  81.  
  82. 				static int gcd(int a ,int b)
  83. 				{
  84. 					if(b==0)
  85. 						return a;
  86. 					else
  87. 						return gcd(b,a%b);
  88. 				}
  89. 			}
  90.  
  91.  
  92. 			/** Faster input **/
  93. 			class Reader
  94. 			{
  95. 			    final private int BUFFER_SIZE = 1 << 16;
  96.  
  97. 			    private DataInputStream din;
  98. 			    private byte[] buffer;
  99. 			    private int bufferPointer, bytesRead;
  100.  
  101. 			    public Reader()
  102. 			    {
  103. 			        din = new DataInputStream(System.in);
  104. 			        buffer = new byte[BUFFER_SIZE];
  105. 			        bufferPointer = bytesRead = 0;
  106. 			    }
  107.  
  108. 			    public Reader(String file_name) throws IOException
  109. 			    {
  110. 			        din = new DataInputStream(new FileInputStream(file_name));
  111. 			        buffer = new byte[BUFFER_SIZE];
  112. 			        bufferPointer = bytesRead = 0;
  113. 			    }
  114.  
  115. 			    public String readLine() throws IOException
  116. 			    {
  117. 			        byte[] buf = new byte[64]; // line length
  118. 			        int cnt = 0, c;
  119. 			        while( (c=read()) != -1) {
  120. 			            buf[cnt++] = (byte)c;
  121. 			            if(c == '\n') break;
  122. 			        }
  123. 			        return new String(buf,0,cnt);
  124. 			    }
  125.  
  126. 			    public int nextInt() throws IOException
  127. 			    {
  128. 			        int ret = 0;
  129. 			        byte c = read();
  130. 			        while (c <= ' ') c = read();
  131. 			        boolean neg = c == '-';
  132. 			        if (neg) c = read();
  133. 			        do {
  134. 			            ret = ret * 10 + c - '0';
  135. 			            c = read();
  136. 			        } while (c >= '0' && c <= '9');
  137. 			        if (neg) return -ret;
  138. 			        return ret;
  139. 			    }
  140.  
  141. 			    public long nextLong() throws IOException
  142. 			    {
  143. 			        long ret = 0;
  144. 			        byte c = read();
  145. 			        while (c <= ' ') c = read();
  146. 			        boolean neg = c == '-';
  147. 			        if (neg) c = read();
  148. 			        do {
  149. 			            ret = ret * 10 + c - '0';
  150. 			            c = read();
  151. 			        } while (c >= '0' && c <= '9');
  152. 			        if (neg) return -ret;
  153. 			        return ret;
  154. 			    }
  155.  
  156. 			    public double nextDouble() throws IOException
  157. 			    {
  158. 			        double ret = 0, div = 1;
  159. 			        byte c = read();
  160. 			        while(c <= ' ') c = read();
  161. 			        boolean neg = c == '-';
  162. 			        if(neg) c = read();
  163. 			        do {
  164. 			            ret = ret * 10 + c - '0';
  165. 			            c = read();
  166. 			        } while (c >= '0' && c <= '9');
  167. 			        if(c == '.')
  168. 			            while((c=read()) >= '0' && c <= '9') {
  169. 			                div *= 10;
  170. 			                ret = ret + (c - '0') / div;
  171. 			            }
  172. 			        if (neg) return -ret;
  173. 			        return ret;
  174. 			    }
  175.  
  176. 			    private void fillBuffer() throws IOException
  177. 			    {
  178. 			        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  179. 			        if (bytesRead == -1) buffer[0] = -1;
  180. 			    }
  181.  
  182. 			    private byte read() throws IOException
  183. 			    {
  184. 			        if (bufferPointer == bytesRead) fillBuffer();
  185. 			        return buffer[bufferPointer++];
  186. 			    }
  187.  
  188. 			    public void close() throws IOException
  189. 			    {
  190. 			        if(din == null) return;
  191. 			        din.close();
  192. 			    }
  193. 			}
  194.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
3
100000 100000
12 24
747794 238336
stdout
copy 
36
6
2
https://ideone.com/wAB2k8
language:
Java (12.0.1)
created:
9 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!