Extend Euclid’s theorem:

For two integers a and b which are not all 0, there must be a set of solutions x and y such that ax+by== GCD (a,b);Copy the code

To achieve the following

int gcd(int a,int b, int& x, int& y){
   int t,d;
   if(b==0) {
       x=1, y=0;   // 1
   	return a;
   }
   d=gcd(b,a%b);
   t=x, x=y;
   y=t-(a/b)*y;  // 2
return d;
}
Copy the code

Personally, I think the first time you see this program, there are two things you don’t understand (see comments), I will explain each of them below

1:

By extending Euclid’s theorem: Ax +by == GCD (a,b) (Equation 1), where b == 0, that is, GCD (a,0) == a. Ax +by == a -> x == 1,y == 0. That should be clear enough

2:

So just to illustrate some of my rules, x and y are the first recursive values, x1 and y1 are the second recursive values. then

The GCD (a, b) = = GCD (a, b, a % b), both in type 1, ax + by = = b * x1 + (a % b) * y1. Let me transform the right

Bx1 + (% b) y1 = = bx1 + (a – b) (a/b) y1 = = ay1 + b (x1 – (a/b) y1), finally got the ax + by = = ay1 + b (x1 – (a/b) * y1)

So that means that x in the previous depth is equal to y1 in the next depth, and y in the previous depth is equal to x1 in the next depth minus a over b times y1. It is important to note that all the divisions used in the derivation above are integral divisions

At this point, we have a set of solutions, x, y, to the infinitive ax+by== GCD (a,b).

So for the ordinary infinitive ax+by==c, what should the solution be. Very simple, x1=x*(c/ GCD (a,b)),y1=y*(c/ GCD (a,b)). That makes sense

If you go a little bit further, you’re going to have a set of solutions that are not going to solve anything in general. No ACM question is that easy… So if we want to get all the solutions, what are all the solutions?

Let’s say d= GCD (a,b). So x=x0+b/dt; y=y0-a/dt; Where t is any constant integer.

How did this come about? I honestly don’t know, so just keep it in mind!

Well, having said all that, talking is not going to help

Let’s start with the simplest problem, PKU 1061 frog’s date

There are two frogs, one at coordinate X and the other at coordinate Y. Frog X can advance m units in a jump, and frog Y can advance n units in a jump. Both frogs are at the same latitude, which is L in length. Two frogs jump and jump in the same direction at the same time, ask you how many times minimum jump before they can meet, if can’t meet, output impossble

Analysis: Suppose that after T jumps, the coordinate of frog 1 is x+mT, and that of frog 2 is y+nT. So the way they can meet is (x+mT) -(y+nT)==P*L, where P is some integer, let me do that

We get (n-m)T+PL == x-y let’s say a=(n-m),b=L,c=x-y,T=x,P=y. So we get ax plus by is equal to equal c. Excited ah, this is not the same above the formula ~

The extended Euclidean function is directly applied to obtain a set of solutions x and y. Since the question is what is the minimum number of jumps, only x is the information we need. So again, is x the smallest?

The answer is probably not! So how do we get the minimum solution? Let’s consider all of the solutions to x: x=x0+b/dt. X0 is what we just found, and it’s clear that there’s a monotone function on the right-hand side, which is the smallest x when t is some number that has the opposite properties of x. Let x’s positive and negative properties be positive, then x is equal to x0 minus b over dt1 (t1==-t). If x is equal to 0, then t is equal to x0 times d over b, and the smallest x is equal to x0 minus t times b over d. This could be a negative x, but if it’s a negative x, let’s add a b over d to it and that’s our answer!

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
usingnamespace std;
 
__int64 x,y,a,b,c,d;
__int64 n,m,X,Y,L;
 
__int64 gcd(__int64 a,__int64 b)
{
    __int64 t,d;
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    d=gcd(b,a%b);
    t=x;
    x=y;
    y=t-(a/b)*y;
    return d;
}
 
int main(a)
{
    while(scanf("%I64d%I64d%I64d%I64d%I64d",&X,&Y,&m,&n,&L)==5)
    {
        a=n-m;
        b=L;
        c=X-Y;
        d=gcd(a,b);
        if(c%d! =0)
        {
            printf("Impossible\n");
            continue;
        }
        x=x*(c/d);
        y=y*(c/d);
 
        X1 =x+b/d*t; y1=y-a/d*t; T is any integer */
        (x+b/d*t) (x+b/d*t
        X -b/d*t =x/(b/d) (x =x/(b/d)
        __int64 k=x*d/b;
        k=x-k*b/d;
        if(k<0)
            k+=b/d;
        printf("%I64d\n",k);
    }
    return0;
}
Copy the code

Let’s do another one that’s a little bit harderpku 2142 the balance

A guy has a scale with only two weights, a and B. Now to weigh an item of weight C, he is asked how much a and B he needs at least. The answer must be the amount of A plus the amount of B and the sum of their weights must be the minimum. (You can hold weights on either plate)

Analysis:

This question I just thought it was a kinetoscope or search, also can be a nose ash.

Let’s say we use x weights for weight A and we use y weights for weight B. So when the balance is balanced, ax plus by should be equal to c. When x and y are positive, they are placed on the other side of c, and when x and y are negative, they are placed on the same side of C.

So the question becomes o | | | x + y | minimum value. X and y are solutions to the infinitive ax+by==c.

I just mentioned that the same formula for all of the solutions of x and y, that is

x=x0+b/d*t

y=y0-a/d*t

All solutions are you subconsciously want to exhaustion, take | | | x + y | the smallest? Obviously doesn’t work, careful analysis: | | | x + y | = = | x0 + b/dt | | + y0 – a/dt |, our regulation (if a < a > b b, we exchange a, b), and from this formula, we can easily find: | x0 + b/dt | is monotone increasing, | y0 – a/dt | is monotone decreasing, and because we set a > b, then cut slope edge should be greater than the slope of increasing, so the entire function reduce than increase fast, but due to the effect of absolute value of the symbol, the final function is increasing. In other words, the function is concave, so it decreases and then increases. When is the smallest? Apparently y0 – a/dt = = 0, so our minimum | | + | y | x also must be near the t = y0d/a, I am in t o ‘clock five points in the range from the smallest (it is said that about a point can be, but I tried it on wa).

#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
usingnamespace std;
#definemin(a,b) a<b? a:b
#definemax(a,b) a>b? a:b
 
int x,y;
int a,b,c;
 
int gcd(int a,int b)
{
    int d;
    if(b==0)
    {
        x=1; y=0;
        return a;
    }
    else
    {
        d=gcd(b,a%b);
        int t=x;
        x=y;
        y=t-(a/b)*y;
    }
    return d;
}
 
int main(a)
{
    int d;
	while(scanf("%d%d%d",&a,&b,&c)! =EOF) {if(! a &&! b &&! c)break;
        int flag=0;
        if(a<b)
        {
            flag=1;
            swap(a,b);
        }
        d=gcd(a,b);
        x=x*c/d; y=y*c/d;
        int t=y*d/a,ans=0xfffffff;
        int x1,y1,x2,y2;
        for(int i=t- 5; i<=t+5; i++) { x2=x+(b/d)*i; y2=y-(a/d)*i;if(abs(x2)+abs(y2)<ans)
            {
                ans=abs(x2)+abs(y2); x1=x2; y1=y2; }}if(! flag)printf("%d %d\n".abs(x1),abs(y1));
        else
            printf("%d %d\n".abs(y1),abs(x1));
    }
    return0;
}
Copy the code

Let’s do something a little harderPKU 2891 Strange Way to Express Integers

You are given a lot of congruences, and you are asked to find a number such that c mod a1 == b1,c mod a2 == b2…. C mod ak==bk (a1,a2,a3…. Ak may not be mutually qualitative)

This is actually the Euclidean solution of the Chinese remainder theorem, if (A1,a2,,,,,ak) two mutually prime, then you can directly apply the formula of the Chinese remainder theorem, but this problem may not be mutually prime. For the first two relations, c % a1 == b1, c % a2 == b2, we can establish the equations a1x+a2y == B2-b1, which is very familiar, we can directly apply the extended Euclidean algorithm to get a set of solutions x,y, and then take the minimum value of x, Substitute c%a1==b1, and you get answer C.

It’s only two formulas, that’s easy, so what about the third one and the fourth one? Just got x has met the first two congruence type, for the new third formula, they get the number must be the front of the requirements of the two formulas, but also meet the requirements of the third new formula, then we will be the first two formulas merged into one formula, with this new formula and the third formula simultaneous solution, and so on, know to work out all the solution formula.

So how do you merge?

The new formula is c1 mod LCM (a1,a2) ==c where c1 is the new answer, c is a solution of the first two expressions, and LCM (a1,a2) is the least common multiple of A1 and a2

You can understand that the new answer c1 is going to mod a1 and mod A2, so mod LCM (a1,ba). And the remainder c is the answer we just got, which means that no matter what we do with C1, we’ll still have a c, which means we won’t ruin what we did!

#include<iostream>
#include<string>
usingnamespace std;
 
__int64 b,b1,c,c1,d,x,y,A,B,C;
 
__int64 gcd(__int64 a,__int64 b)
{
    __int64 d,t;
    if(! b) { x=1;
        y=0;
        return a;
    }
    d=gcd(b,a%b);
    t=x;
    x=y;
    y=t-(a/b)*y;
    return d;
}
 
int main(a)
{
    int k,i,flag;
    freopen("in.txt"."r",stdin);
    while(scanf("%d",&k)! =EOF) { flag=0;
        scanf("%I64d%I64d",&b,&c);
        if(k==1)
        {
            printf("%I64d\n",b+c);
            continue;
        }
        for(i=1; i<k; i++) {scanf("%I64d%I64d",&b1,&c1);
            if(flag)
                continue;
            A=b; B=b1; C=c1-c;
            d=gcd(A,B);
            if(C%d! =0)
            {
                flag=1;
                continue;
            }
            x=x*C/d; // Obtain the minimum value of x
            x=x-(x*d/B)*(B/d);
            if(x<0)
                x+=B/d;
            c=x*b+c; b=(b*b1)/d; // Combine the first two statements of the analysis
        }
        if(! flag) {printf("%I64d\n",c);
        }
        else
        {
            printf("-1\n");
        }
    }
    return0;
}
Copy the code