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.
Constraints
- 1≤T≤1000
- 1≤A,B≤109
- A≠B
Sample 1:
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:
