FIND_X - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: shubham_grg
Testers: iceknight1093, tabr
Editorialist: iceknight1093

DIFFICULTY:

1651

PREREQUISITES:

Basic math

PROBLEM:

Given integers A, B, C, D such that A\bmod B = C\bmod D, find the smallest positive integer X such that (A+X)\bmod B = (C+X)\bmod D

EXPLANATION:

tl;dr

The answer is either 1 or \text{lcm}(B, D) - (A\bmod C).


First, notice that the actual values of A and C don’t matter: only their remainders when divided by B and D, respectively.
So, let’s replace A with (A\bmod B) and C with (C\bmod D). In particular, this ensures that A\lt B, C\lt D, and A = C.

Now, note that a lot of the time we can just choose X = 1.
In fact, as long as A+1 \lt B and C+1 \lt D, we can choose X = 1 (since A = C, A+1 = C+1 and both these values don’t exceed their respective modulos).
X = 1 also works when both A+1 = B and C+1 = D hold, since both values become 0 in that case.

So, we only need to solve for the case when X = 1 doesn’t work, i.e, exactly one of A = B-1 or C = D-1 holds.

Let’s do a bit of math.
Consider an integer X for which equality holds.
We have (A+X)\bmod B = (C+X)\bmod D.

Writing out this in terms of remainders, there exist three integers p, q, r such that

  • A+X = pB + r
  • C+X = qD + r
    Note that r is common.

It’s clearly optimal to choose r = 0 (if it was anything higher, X - 1 would work too so X wouldn’t be minimal).

This gives us A+X = pB and C+X = qD.
However, notice that we have A = C (from our replacement in the very first step), so this means A+X = pB = qD.

In particular, A+X must be a multiple of both B and D.
The smallest such integer is, by definition, \text{lcm}(B, D).

So, we can choose X+A = \text{lcm}(B, D), which gives us X = \text{lcm}(B, D) - A as our answer.

TIME COMPLEXITY

\mathcal{O}(\log\min(B,D)) per test case.

CODE:

Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;

#define ll long long int

int main() {
	// your code goes here
	
	int t; cin>>t;
	assert(t<=1e5);
	while(t--)
	{
	    ll A, B, C, D; cin>>A>>B>>C>>D;
	    
	    assert(A>0 && A<=1e9);
	    assert(B>0 && B<=1e9);
	    assert(C>0 && C<=1e9);
	    assert(D>0 && D<=1e9);
	    assert(A%B==C%D);
	    
	    A%=B, C%=D;
	    
	    

	    if((A+1)%B==(C+1)%D) cout<<"1\n";
	    else 
	    {
	        ll ans=B*D/__gcd(B, D)-A;
	        cout<<ans<<"\n";
	    }
	}
	
	
	return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
    string buffer;
    int pos;

    const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    const string number = "0123456789";
    const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string lower = "abcdefghijklmnopqrstuvwxyz";

    input_checker() {
        pos = 0;
        while (true) {
            int c = cin.get();
            if (c == -1) {
                break;
            }
            buffer.push_back((char) c);
        }
    }

    string readOne() {
        assert(pos < (int) buffer.size());
        string res;
        while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
            res += buffer[pos];
            pos++;
        }
        return res;
    }

    string readString(int min_len, int max_len, const string& pattern = "") {
        assert(min_len <= max_len);
        string res = readOne();
        assert(min_len <= (int) res.size());
        assert((int) res.size() <= max_len);
        for (int i = 0; i < (int) res.size(); i++) {
            assert(pattern.empty() || pattern.find(res[i]) != string::npos);
        }
        return res;
    }

    int readInt(int min_val, int max_val) {
        assert(min_val <= max_val);
        int res = stoi(readOne());
        assert(min_val <= res);
        assert(res <= max_val);
        return res;
    }

    long long readLong(long long min_val, long long max_val) {
        assert(min_val <= max_val);
        long long res = stoll(readOne());
        assert(min_val <= res);
        assert(res <= max_val);
        return res;
    }

    vector<int> readInts(int size, int min_val, int max_val) {
        assert(min_val <= max_val);
        vector<int> res(size);
        for (int i = 0; i < size; i++) {
            res[i] = readInt(min_val, max_val);
            if (i != size - 1) {
                readSpace();
            }
        }
        return res;
    }

    vector<long long> readLongs(int size, long long min_val, long long max_val) {
        assert(min_val <= max_val);
        vector<long long> res(size);
        for (int i = 0; i < size; i++) {
            res[i] = readLong(min_val, max_val);
            if (i != size - 1) {
                readSpace();
            }
        }
        return res;
    }

    void readSpace() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == ' ');
        pos++;
    }

    void readEoln() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == '\n');
        pos++;
    }

    void readEof() {
        assert((int) buffer.size() == pos);
    }
};

pair<long long, long long> inv_gcd(long long a, long long b) {
    a = a % b;
    if (a == 0) {
        return {b, 0};
    }
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;
    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if (m0 < 0) {
        m0 += b / s;
    }
    return {s, m0};
}

pair<long long, long long> crt(vector<long long> r, vector<long long> m) {
    int n = (int) r.size();
    long long r0 = 0, m0 = 1;
    for (int i = 0; i < n; i++) {
        long long r1 = r[i] % m[i], m1 = m[i];
        if (m0 < m1) {
            swap(r0, r1);
            swap(m0, m1);
        }
        if (m0 % m1 == 0) {
            if (r0 % m1 != r1) {
                return {0, 0};
            }
            continue;
        }
        long long g, im;
        tie(g, im) = inv_gcd(m0, m1);
        long long u = (m1 / g);
        if ((r1 - r0) % g) {
            return {0, 0};
        }
        long long x = (r1 - r0) / g % u * im % u;
        r0 += x * m0;
        m0 *= u;
        if (r0 < 0) {
            r0 += m0;
        }
    }
    return {r0, m0};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    input_checker in;
    int tt = in.readInt(1, 1e5);
    in.readEoln();
    while (tt--) {
        long long a = in.readLong(1, 1e9);
        in.readSpace();
        long long b = in.readLong(1, 1e9);
        in.readSpace();
        long long c = in.readLong(1, 1e9);
        in.readSpace();
        long long d = in.readLong(1, 1e9);
        in.readEoln();
        a %= b;
        c %= d;
        assert(a == c);
        if ((a + 1) % b == (c + 1) % d) {
            cout << 1 << '\n';
            continue;
        }
        a = (b - a) % b;
        c = (d - c) % d;
        auto p = crt({a, c}, {b, d});
        if (!p.first) {
            p.first += p.second;
        }
        cout << p.first << '\n';
    }
    in.readEof();
    return 0;
}
Editorialist's code (Python)
import math
for _ in range(int(input())):
    a, b, c, d = map(int, input().split())
    if (a+1)%b == (c+1)%d: print(1)
    else: print(b*d//math.gcd(b, d) - a%b)
5 Likes

it is given in the question that a%b == c%d, read again properly

tl;dr a%b not c

this was the only problem i didn’t get - gotta work on number theory ig, but thanks for the explanation ;D

A=C i didnt understand this

A\%B = C\%D, as given in the statement and constraints.
If you take A modulo B and C modulo D, obviously A and C will now be equal right?
That’s literally what the first equation says, after all.

2 Likes

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios ::sync_with_stdio(false);
cin.tie(NULL);
long long t;
cin >> t;
while (t–)
{
long long a, b, c, d;
cin >> a >> b >> c >> d;
if (a+1<b && c+1<d){
cout<<1<<endl;
}
else{
long long x = a%b;
long long y = b*d/__gcd(b,d);
cout<<y-x<<endl;
}
}
return 0;
}
can any body tell , why this ain’t working?

#include
#include

using namespace std;

int main() {
int t{};
cin>>t;

for(int i=0;i<t;i++)
{
int a{},b{},c{},d{};
cin>>a>>b>>c>>d;
if(((a+1)%b)==((c+1)%d))
{
    cout<<"1"<<endl;
}


else
{
    cout<<lcm(b,d)-(a%b)<<endl;
}
}

return 0;

}
Can anyone tell what’s wrong in this?

Plz explain why replacing int with long int in this code, it finally works?

How can be A == C true when A%B==C%D true?

Can anyone share some test cases where various solutions might fail?

Read my comment again, I said A and C will be equal after you take A modulo B and C modulo D.

Basically, the constraint says that A\% B = C\% D.
So if you do

A %= B;
C %= D;

of course A and C are now equal, right?

Writing out this in terms of remainders, there exist three integer
p,q,r such that
A+X=pB+r
C+X=qD+r
Note that r is common.
It’s clearly optimal to choose r=0 (if it was anything higher, X−1 would work too so
X wouldn’t be minimal).

pls explain this.