Introduction
This post is about div 2 question A from Round 406 http://codeforces.me/problemset/problem/787/A. Coding the solution is easy however figuring out why this solution works requires a bit more thought.
The Situation
The question boils down to having four fixed integers a, b, c, d all between 1 and 100 and finding the smallest non-negative integer pairs m, n such that b + an = d + cm. A solution that works is to brute force all integer pairs in [0, 200] × [0, 200]. (The editorial says sticking with pairs [0, 100] × [0, 100] is sufficient but the proof in this case given is simpler).
The Technique Overview
If we want to brute force enough pairs to either find a solution or conclude that one does not exist we need to know how many pairs are enough. It turns out a technique in number theory can help us. The idea assume we have a solution to our equation and use it to generate more solutions. Usually in number theory this is used to show if a particular equation has one solution it has infinitely many and the next step is to find a single solution for the equation and then conclude it has infinitely many. In our case we assume we have a large solution and show it can be used to generate a smaller solution.
The Technique in Action
Assume we have a pair (n0, m0) such that b + n0a = d + m0c. Let's perturb our n0 by adding an integer h to it. Then we have b + (n0 + h)a = d + m0c + ha. We would like to combine the last two terms on the right hand side so we let h = tc for some integer t. Then we have b + (n0 + tc)a = d + (m0 + ta)c. Thus given a solution (n0, m0) the pair (n0 + tc, m0 + ta) is another solution for all integers t.
Next we assume we have a solution (n0, m0) where n0 > 200 and show the smaller solution (n0 - c, m0 - a) is positive. This allows us to restrict our search to solutions to those with values between 0 and 200 inclusive. First we note since c ≤ 100 we have n0 - c > 100. Thus the first term is positive. For the second term we note since this new pair is a solution we have b + (n0 - c)a = d + (m0 - a)c. Since c > 0 it is sufficient to prove (m0 - a)c > 0. Also since a > 0, b > 0 and n0 - a > 100 we can conclude the left hand side of the equation is greater than 100. Thus d + (m0 - a)c > 100. Finally since d ≤ 100 we conclude (m0 - a) > 0 as required.
Did I figure all this our during the contest?
I did not. Once I could not see a simple way to generate the answer I decided to brute force. I suspected something like what I described above would occur and brute forced all pairs in [0, 999] × [0, 999]. Fortunately for me doing this worked. My contest submission is below.
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
#include<string>
#include<set>
#include<queue>
using namespace std;
int main(){
int a,b,c,d;
cin>>a>>b>>c>>d;
for(int i=0; i<1000; i++){
for(int j=0; j<1000; j++){
if(b+a*i==d+c*j){
cout<<b+a*i;
return 0;
}
}
}
cout<<-1;
return 0;
}