PROBLEM LINK:
Author: ultimate_st
Tester: chef_oggy
Editorialist: ultimate_st
DIFFICULTY:
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[1] 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] = 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)
{
ret.add(spf[x]);
x = x / spf[x];
}
return ret;
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
FastReader sc=new FastReader();
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);
}
}
}
class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
}
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 {
str = br.readLine();
}
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[100007]; ll Size[100007];
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] = 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;
}