# FIND_X - Editorial

Author: shubham_grg
Testers: iceknight1093, tabr
Editorialist: iceknight1093

1651

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() {

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);
}
}

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);
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);
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);
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++) {
if (i != size - 1) {
}
}
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++) {
if (i != size - 1) {
}
}
return res;
}

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

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

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;
while (tt--) {
long long a = in.readLong(1, 1e9);
long long b = in.readLong(1, 1e9);
long long c = in.readLong(1, 1e9);
long long d = in.readLong(1, 1e9);
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';
}
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?

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.