Number Theory technique and Monster

Revision en2, by usernameson, 2017-03-24 10:19:02

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] × [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; }
Tags mathematics, number theory, brute force

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English usernameson 2017-03-24 10:19:02 2 Tiny change: ' integers t.\n\nNext ' -> ' integers $t$.\n\nNext ' (published)
en1 English usernameson 2017-03-24 10:14:16 3231 Initial revision (saved to drafts)