Introduction

This post is about div 2 question A from Round 406 http://mirror.codeforces.com/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 (n₀, m₀) such that b + n₀a = d + m₀c. Let's perturb our n₀ by adding an integer h to it. Then we have b + (n₀ + h)a = d + m₀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₀ + tc)a = d + (m₀ + ta)c. Thus given a solution (n₀, m₀) the pair (n₀ + tc, m₀ + ta) is another solution for all integers t.

Next we assume we have a solution (n₀, m₀) where n₀ > 200 and show the smaller solution (n₀ - c, m₀ - 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 n₀ - 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₀ - c)a = d + (m₀ - a)c. Since c > 0 it is sufficient to prove (m₀ - a)c > 0. Also since a > 0, b > 0 and n₀ - a > 100 we can conclude the left hand side of the equation is greater than 100. Thus d + (m₀ - a)c > 100. Finally since d ≤ 100 we conclude (m₀ - 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;
}