# CPAIR - Editorial

Author: ultimate_st
Tester: chef_oggy
Editorialist: ultimate_st

MEDIUM

# PROBLEM:

Given a pair of integers (a, b) which represents a message, and the message can be decoded by finding the value of x (x>0) that must be added to both a and b in order to make them non-coprime.

# Prerequisites:

• Sieve
• A pinch of mathematics # Hint

Since a,b \leq 10^6 you will precompute a sieve of smallest prime factors and you have to obtain factorization in O(log n).

# QUICK EXPLANATION:

The problem is about decoding messages represented by pairs of integers (a, b), where the values of a and b need to be modified by adding a positive integer x to both of them to make them non-coprime. We can solve this problem by implementing a prime factorization algorithm using the sieve of Eratosthenes and finding the minimum value of x required to make a and b non-coprime. It can be done by finding the prime factors of the difference between a and b, and then finding the minimum value of x that satisfies the condition by checking each factor. If the absolute difference between a and b is 1, then the code outputs -1 since it is impossible to make them non-coprime by adding a positive integer.

# EXPLANATION:

We know that the gcd of two numbers divides their difference. Therefore, if we compute the difference d between a and b, then any common divisor of a+x and b+x must also divide d. Therefore, we can factorize d by precomputing sieve before test cases loop. Then we can factorize d in O(log d) time.

For each prime factor p[i] , we calculate the remainder of a divided by p[i]. This is done to find the smallest integer k such that a + k is divisible by p[i] . We then subtract a%p[i] from p[i] to get the difference between a and the nearest multiple of p[i] that is greater than a . This gives us the value of k that satisfies the condition that a+k is divisible by p[i] . We take the minimum of min and this value of k for all prime factors p[i] of d . The resulting value of min is the minimum value of x that satisfies the condition that a+x and b+x are non-coprime.

For computing factorization using sieve ,we create an array spf of size 10^6+1, where spf[i] represents the smallest prime factor of i. We start by initializing spf as 1, as 1 is not a prime number. We then mark the smallest prime factor of every number i to be itself, i.e. spf[i] = i. We then mark the smallest prime factor of every even number to be 2.

Next, we loop through every odd number from 3 to sqrt(n) and check if it is a prime number by checking if spf[i] == i. If i is a prime number, we mark the smallest prime factor of all its multiples as i, unless it has already been marked as a smaller prime factor. This way, we calculate the smallest prime factor of every number in the range from 1 to n.

The getFactorization method takes a number x as input and returns a vector containing the prime factorization of x. We start by dividing x by its smallest prime factor, which we can find using the spf array. We then keep dividing x by its smallest prime factor until we can no longer do so. We add each smallest prime factor to a vector and return the vector once we have completely factorized x.
The time complexity of getFactorization method will be O(log n) and that of sieve will be O(nloglogn).

# SOLUTIONS:

Setter's Solution
/* package codechef; // don't place package name! */

import java.util.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class cac
{
static final int MAXN = 1000001;

static int spf[] = new int[MAXN];

static void sieve()
{
spf = 1;
for (int i=2; i<MAXN; i++)
spf[i] = i;

for (int i=4; i<MAXN; i+=2)
spf[i] = 2;

for (int i=3; i*i<MAXN; i++)
{
if (spf[i] == i)
{
for (int j=i*i; j<MAXN; j+=i){
if (spf[j]==j)
spf[j] = i;
}
}
}
}
static ArrayList<Integer> getFactorization(int x)
{
ArrayList<Integer> ret = new ArrayList<>();
while (x != 1)
{
x = x / spf[x];
}
return ret;
}
public static void main (String[] args) throws java.lang.Exception
{
int t=sc.nextInt();
sieve(); //precomputation

ab:while(t-->0){
int a=sc.nextInt();
int b=sc.nextInt();
if(Math.abs(a-b)==1){
System.out.print(-1+"\n");
continue ab;
}
int d=Math.abs(b-a);
ArrayList<Integer> p = getFactorization(d);
int min=Integer.MAX_VALUE;
for (int i=0; i<p.size(); i++)
{
min=Math.min(min,p.get(i)-(a%p.get(i)));
}
System.out.println(min);
}
}
}

StringTokenizer st;
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
}
catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
}
catch (IOException e) {
e.printStackTrace();
}
return str;
}
}

Tester's Solution
                       //The more you know, the more you don't know//
#include <bits/stdc++.h>

#define loop(i,m,n) for(ll i=m;i<n;i++)
#define rev(i,m,n) for(ll i=m;i>=n;i--)
#define ll long long
#define in(n) cin>>n
#define out(n) cout<<n<<"\n"
#define o(n) cout<<n<<" "
#define nl cout<<"\n"
#define yes cout<<"YES"<<"\n"
#define no cout<<"NO"<<"\n"
#define pb push_back
#define ppb pop_back
#define size(x) x.size()
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define SUM(x) accumulate(all(x), 0LL)
#define SORT(x) is_sorted(all(x))
#define lcm(x,y) (x*y)/__gcd(x,y)
#define dgt(n) floor(log10(n)+1)
#define point cout<<fixed<<setprecision(10)
#define debug(x) cout<<#x<<" "<<x<<"\n";
#define print(v) for(auto x : v)  o(x);  nl;
#define ub(v,val) upper_bound(all(v),val)-v.begin()
#define lb(v,val) lower_bound(all(v),val)-v.begin()
const long long M = 1e9 + 7;
const long long inf = LONG_LONG_MAX;

using namespace std;

//--------------------[...Never Used Functions...]---------------------//
ll binpow(ll a, ll b){   ll res=1;      while(b>0){     if(b&1) res=res*a;    a=a*a; b>>=1;    }       return res;     }
ll powmod(ll a, ll b, ll m) {ll ans = 1; while (b) {if (b & 1) {ans = (ans * a) % m;} a = (a * a) % m; b = b >> 1;} return ans % m;}
vector<ll> div(ll n){   vector<ll> v;   for(int i=1; i<=sqrt(n); i++){     if (n%i == 0){   v.pb(i);    if(n/i!=i) v.pb(n/i);  }   }   return v;   }
vector<ll> primediv(ll n){  vector<ll> v;   for(ll i=2;i<=sqrt(n);i++){   while(n%i==0){ n=n/i; v.pb(i); }  }   if(n>1) v.pb(n);    return v;   }
ll modINV(ll n,ll mod){      return powmod(n,mod-2,mod);    }
ll ncrmod(ll n,ll r,ll p){  if(r==0)     return 1;   unsigned long long fac[n + 1]={1};  for(int i=1;i<=n;i++)    fac[i]=(fac[i-1]*i)%p;  return (((fac[n]*modINV(fac[r],p))%p)*modINV(fac[n-r],p))%p;  }
double logg(ll n,ll k){   return log2(n)/log2(k);   }
//---------------------------------------------------------------------//

/*------------------------[...DSU...]------------------------//
ll parent;   ll Size;
void make(ll v){   parent[v]=v;    Size[v]=1;  }
ll find(ll v){    if(v==parent[v])    return v;       return parent[v] = find(parent[v]);     }
void Union(ll a,ll b){   a = find(a);    b = find(b);    if(a!=b){   if(Size[a] < Size[b])   swap(a,b);      parent[b] = a;      Size[a] += Size[b];     }      }
//----------------------------------------------------------*/

#define MAXN   1000001
int spf[MAXN];

void sieve()
{
spf = 1;
for (int i=2; i<MAXN; i++)
spf[i] = i;

for (int i=4; i<MAXN; i+=2)
spf[i] = 2;

for (int i=3; i*i<MAXN; i++)
{
if (spf[i] == i)
{
for (int j=i*i; j<MAXN; j+=i)
if (spf[j]==j)
spf[j] = i;
}
}
}

vector<int> getFactorization(int x)
{
vector<int> ret;
while (x != 1)
{
ret.push_back(spf[x]);
x = x / spf[x];
}
return ret;
}

void drizzle()
{
ll a,b;     in(a>>b);

if(min(a,b)==max(a,b)-1)
{
out(-1);
}
else
{
if(a%2==b%2)
{
if(b&1)     out(1);
else
{
if(__gcd(a+1,b+1)!=1)       out(1);
else        out(2);
}
}
else
{
ll n=max(a,b)-min(a,b);
vector<int> factors = getFactorization(n);

ll res=inf;
for(auto x : factors)
{
res=min(res,x-(min(a,b)%x));
}

if(res==inf)    out(n);
else            out(res);
}
}

return;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

int testcase=1;
cin>>testcase;

sieve();

while(testcase--)
{
drizzle();
}

return 0;
}