Possible GCD Solution Codechef

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
  • AB

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:

Leave a Comment

twelve + nine =