参考博文： 数论:欧几里得与扩展欧几里得算法
参考博文： 当我真正理解了扩展欧几里得定理

扩展欧几里得方法：
大概思路 ：

• 第一步 ： 给出方程 ax + by = c 。 （或ax = c(mod b))。
• 第二步 ： 算出辗转相除法 gcd(a, b) 。
• 第三步 ： 运用扩展欧几里德 ex_gcd（a, b）-> ax + by = gcd(a,b) 的 一组解（x, y）。（实际上，可以使用exgcd一起算出gcd(a, b)，省去了第二步）。
• 第三步： 根据 c % gcd(a, b) 判断是否 ax + by = c 有解 。
• 第四步 ： 根据 ax + by = c 的通解公式 x1 = (x + k * ( b / gcd(a, b) )) * (c / gcd(a, b) 令 b1 = b / gcd(a, b) , 所以 x1 的 最小正整数解 为 ： x1 = (x1 % b1 + b1) % b1, 对应的 y1 = （c - a*x1） / b。

青蛙约会

题目链接：青蛙约会
参考博文：挑战程序设计竞赛:青蛙的约会
重点掌握扩展欧几里得的转换和求解方法。
主要问题：

• 求解x和y。方法
• 判断是否存在该条件。

The Balance

题目链接：The Balance
一个扩展欧几里得题目，目标在于x和y之和要小，这需要保证重量小的砝码取值尽可能少，以至于趋近与0，所以我们必须从一开始就确定哪一方的单个砝码重量小。具体参考博文当我真正理解了扩展欧几里得定理。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;
LL a, b, d, x, y, p, q, cntx, cnty;

LL extgcd(LL a, LL b, LL &x, LL &y)
{
    
    LL d = a;
    if(b!=0)
    {
    
        d = extgcd(b, a%b, y, x);
        y -= (a/b)*x;
    }
    else
    {
    
        x = 1, y = 0;
    }
    return d;
}

int main()
{
    
    while(scanf("%lld%lld%lld", &a, &b, &d)!=EOF && (a+b+d))
    {
    
        int flag = 0;

        //保证a一定大于b方便下面取值
        if(a<b)
        {
    
            flag = 1;
            swap(a, b);
        }
        
        //x和y的正负值只表示在天平的哪一方
        LL u = extgcd(a, b, x, y);
        x = x*d/u, y = y*d/u;

        LL Min = 1<<29, t;
        //尽可能减少重量小的砝码的数量
        t = y*u/a;

        for(LL i=t-5; i<=t+5; i++)
        {
    
            p = abs(x+(b/u)*i);
            q = abs(y-(a/u)*i);
           
            if(p+q<Min)
            {
    
                cntx = p;
                cnty = q;
                Min = p+q;
            }
        }
        if(!flag)
            printf("%lld %lld\n", cntx, cnty);
        else
            printf("%lld %lld\n", cnty, cntx);
    }
    return 0;
}

Strange Way to Express Integers

题目链接：Strange Way to Express Integers
中国剩余定理的模板题，即求c%a1=r1、c%a2=r2、c%a3=r3等多个式子中的c值，其中ai和ri给出。

• 思路：可以将c作为桥梁，得到a1$\times$X+r1=a2$\times$Y+r2，即a1$\times$X-a2$\times$Y=r2-r1，可以将Y=-Y带入（最后求出Y时取反即可），得到a1$\times$X+a2$\times$Y=r2-r1，这是一个标准的扩展欧几里得公式，a=a1，b=a2，c=r2-r1。
  本题的重点在于联立多个式子。假定我们已经求出第一个式子的解，对于a1$\times$X+r1=a2$\times$Y+r2,已经得出X和Y的值，即可以求出c1=a1$\times$X+r1。接下来需要做的是把这两个式子转化为一个式子。即c2%lcm(a1,a2)=c，lcm(a1,a2)是a1和a2的最小公倍数，可以理解为新的答案c2即要mod a1,又要mod a2,所以就mod lcm(a1,ba)。而余数c 是刚前面求得的答案，也就是说c1不管怎么折腾，都还会保留一个c，即c2%a1=c%a1=b1，可知没有改变之前的情况。
  所以更新的情况为r1 = a$\times$X+r1，a=a$\times$b/d，（d是a和b的最大公约数），然后b = a3, c = r2-r1。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include<string>
using namespace std;

typedef __int64 LL;//与long long 一样
LL k, a, r1, b, r2, c, x, y;

LL extgcd(LL a, LL b, LL &x, LL &y)
{
    
    LL d = a;
    if(b!=0)
    {
    
        d = extgcd(b, a%b, y, x);
        y -= (a/b)*x;
    }else{
    
        x = 1, y = 0;
    }
    return d;
}

int main()
{
    
    while(scanf("%I64d", &k)!=EOF)
    {
    
        int flag = 0;
        scanf("%I64d%I64d", &a, &r1);
        if(k==1)
        {
    
            printf("%I64d\n", a+r1);
            continue;
        }
        for(int i=1; i<k; i++)
        {
    
            scanf("%I64d%I64d", &b, &r2);
            if(flag) continue;
            c = r2-r1;

            LL d = extgcd(a, b, x, y);

            if(c%d)
            {
    
                flag = 1;
                continue;
            }
            //根据c值调整x，y解的大小
            x = x*c/d;
            LL t = b/d;
            x = (x%t+t)%t;//获取最小正整数解
            /*
            采用这种方法会溢出，推荐上面的方法
            LL t = -(d/b)*x;
            x = x+t*b/d;
            if(x<0) x += b/d;*/
            r1 = x*a+r1; a = (a*b)/d;
        }
        if(flag)
            printf("-1\n");
        else
            printf("%I64d\n", r1);
    }
    return 0;
}