Editorialist: akshayakgec
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Basic modulo and number theory
PROBLEM:
You are given two numbers XX & YY (XX != YY) your task is to determine count of such positive numbers KK that the remainders of X and Y when divided by K are the same. More formally you need to determine count of such K (K > 0) that X % K == Y % K .
EXPLANATION:
If x and y are not equal then our answer will be the total number of factors absolute difference of x and y.
between x and y.
Given:- (x % k) = (y % k)
((x % k)- (y % k)) = 0
((x % k) - (y % k)) % k=0 % k
We know the property of modulo- ((a % k) - (b % k)) % k = (a - b) % k;
(x - y) % k = 0
If (x - y) is a multiple of k then their modulo will be 0
We have to find the total number of factors of the absolute difference of x and y.
Editorialist's Solution
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
ll x,y;
cin >> x >> y;
ll k;
int cnt = 0;
k = abs(x - y);
for(ll i=1; i<=sqrt(k); i++) {
if(k % i == 0){
cnt++;
if(k / i != i)
{
cnt++;
}
}
}
cout << cnt << "\n";
}
return 0;
}