SPOJ 7718. Number of common divisors Solution

 

Problem Statement:
 You will be given T (T<=10^6) pair of numbers. All you have to tell is the number of common divisors between two numbers in each pair.


Input
First line of input: T (Number of test cases)In next T lines, each have one pair A B (0<A,B<=10^6)

Output

One integer describing number of common divisors between two numbers.

Example

Input:
3
100000 100000
12 24
747794 238336
Output:

36
6
2

Solution :

#include <cstdio>
#include <iostream>

using namespace std;
#define max 1001
#define sz 35
bool pp[max+1];
long p[max],ind=0;

void sieve(){
 long i,j,k,l;

 p[ind++] = 2;
 for( i = 4; i <= max; i += 2)
  pp[i] = true;
 for(i = 3; i <= max;i += 2){
  if(!pp[i]){
   p[ind++] = i;
   for(j = i * i;j <= max; j += i)
    pp[j] = true;
  }
 }
}
long gcd(long a, long b){
 return (b == 0 ? a:gcd(b, a%b));
}

int main(){
 long i,j,k,l,t,a,b,ans,tmp,cnt;

 sieve();

 scanf("%ld",&t);
 while(t--){
  scanf("%ld %ld",&a,&b);
  tmp = gcd(a,b);
  if(tmp == 1){
   printf("1\n");
   continue;
  }
  i = 0;
  ans = 1;
  while(tmp && p[i] <= tmp && i < ind){
   cnt = 0;
   while(tmp % p[i] == 0){
    tmp /= p[i];
    cnt++;
   }
   ans *= (cnt+1);
   i++;
  }
  if(tmp>1)
   ans <<= 1;
  printf("%ld\n",ans);
 }
 return 0;
}