#### Introduction↵
This post is about div 2 question A from Round 406 http://codeforces.net/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] \times [0,200]$. (The editorial says sticking with pairs $[0,100]\times[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 $(n_{0}, m_{0})$ such that $b+n_{0}a=d+m_{0}c$. Let's perturb our $n_{0}$ by adding an integer $h$ to it. Then we have $b+(n_{0}+h)a=d+m_{0}c+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+(n_{0}+tc)a=d+(m_{0}+ta)c$. Thus given a solution $(n_{0},m_{0})$ the pair $(n_{0}+tc,m_{0}+ta)$ is another solution for all integerst$t$.↵
↵
Next we assume we have a solution $(n_{0},m_{0})$ where $n_{0}>200$ and show the smaller solution $(n_{0}-c,m_{0}-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\leq 100$ we have $n_{0}-c >100$. Thus the first term is positive. For the second term we note since this new pair is a solution we have $b+(n_{0}-c)a=d+(m_{0}-a)c$. Since $c>0$ it is sufficient to prove $(m_{0}-a)c>0$. Also since $a>0$, $b>0$ and $n_{0}-a >100$ we can conclude the left hand side of the equation is greater than 100. Thus $d+(m_{0}-a)c>100$. Finally since $d\leq 100$ we conclude $(m_{0}-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] \times [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;↵
}↵
↵
~~~~~↵
This post is about div 2 question A from Round 406 http://codeforces.net/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] \times [0,200]$. (The editorial says sticking with pairs $[0,100]\times[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 $(n_{0}, m_{0})$ such that $b+n_{0}a=d+m_{0}c$. Let's perturb our $n_{0}$ by adding an integer $h$ to it. Then we have $b+(n_{0}+h)a=d+m_{0}c+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+(n_{0}+tc)a=d+(m_{0}+ta)c$. Thus given a solution $(n_{0},m_{0})$ the pair $(n_{0}+tc,m_{0}+ta)$ is another solution for all integers
↵
Next we assume we have a solution $(n_{0},m_{0})$ where $n_{0}>200$ and show the smaller solution $(n_{0}-c,m_{0}-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\leq 100$ we have $n_{0}-c >100$. Thus the first term is positive. For the second term we note since this new pair is a solution we have $b+(n_{0}-c)a=d+(m_{0}-a)c$. Since $c>0$ it is sufficient to prove $(m_{0}-a)c>0$. Also since $a>0$, $b>0$ and $n_{0}-a >100$ we can conclude the left hand side of the equation is greater than 100. Thus $d+(m_{0}-a)c>100$. Finally since $d\leq 100$ we conclude $(m_{0}-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] \times [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;↵
}↵
↵
~~~~~↵
