# Possible GCD Solution Codechef

Page Contents

## Possible GCD Solution Codechef

Chef has two distinct positive integers A and B.

Chef wonders how many distinct values are possible for the expression gcd(A+X,B+X), where X can take any non-negative integer value.

Help Chef find this value.

Here, gcd stands for Greatest Common Divisor.

### Input Format

• The first line contains a single integer T — the number of test cases. Then the test cases follow.
• The first and only line of each test case contains two distinct space separated integers A and B.

### Output Format

For each testcase, output the number of distinct values of the expression gcd(A+X,B+X), where X can take any non-negative integer value.

• 1≤T≤1000
• 1≤A,B≤109
• AB

Input

```2
1 2
12 8
```

Output

```1
3
```

### Explanation:

Test case 1: Here gcd(1+X,2+X)=1 no matter what value of X you choose.

Test case 2:

• If we take X = 0, gcd(12,8)=4.
• If we take X = 1, gcd(13,9)=1.
• If we take X = 2,  gcd(14,10)=2.

It can be shown that no other value of gcd is possible.

## SOLUTION

Program: Possible GCD Solution in Python

```for _ in range(int(input())):
a,b = map(int,input().split())
num = abs(a-b)
a = 0

for i in range(1, int(pow(num,0.5))+1):
if num%i ==0:
a+=1
if i !=num//i:
a+=1
print(a)```

Program: Possible GCD Solution in C++

```#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin >> t;
while (t--)
{
int a, b;
cin >> a >> b;
int d = 0, c = abs(a - b);

for (int i = 1; i * i <= c; i++)
{
if (c % i == 0)
{
d++;
if (c / i != i)
{
d++;
}
}
}
cout << d << endl;
}
return 0;
}```

Program: Possible GCD Solution in Java

```import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef {
public static void main(String[] args) throws java.lang.Exception {
Scanner scn = new Scanner(System.in);
int t = scn.nextInt();
while (t-- > 0) {
int a = scn.nextInt();
int b = scn.nextInt();
int dif = Math.abs(a - b);
int ans = 0;
for (int i = 1; i * i <= dif; i++) {
if (dif % i == 0) {
if (dif / i == i) ans++;
else ans += 2;
}
}
System.out.println(ans);
}
}
}```

Related: