扩展欧几里得

扩展欧几里得的目的就是求乘法逆元，想要学扩展欧几里得首先要了解群论，了解群论，了解群论！ 重要的事情说三遍。

模板

long long ex_gcd(long long a, long long b, long long &x, long long &y){
    if(b == 0){
        x = 1, y= 0;
        return a;
    }else{
        long long r = ex_gcd(b, a% b, y, x);
        y -= x*(a/b);
        return r;
    }
}

POJ 1061 青蛙的约会

这道题涉及的点也是对群论的考察，了解群论的特性的话这道题就变成一道水题了

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>

using namespace std;
long long ex_gcd(long long a, long long b, long long &x, long long &y){
    if(b == 0){
        x = 1, y= 0;
        return a;
    }else{
        long long r = ex_gcd(b, a% b, y, x);
        y -= x*(a/b);
        return r;
    }
}
int main(){
    long long x, y, m, n, l;
    while(scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &l)!=EOF){
        long long a = (m - n+l)%l;
        long long b = (y - x + l ) % l;
        long long c = __gcd(a, l);
        if(b % c != 0){
            printf("Impossible\n");
            continue;
        }
        a = a / c; b = b / c;
        l /= c;
        //printf("%lld %lld %lld\n", a, b, l);
        ex_gcd(a, l, x, y);
        x = (x+l) % l;
        x*= b;
        x %= l;
        printf("%lld\n", x);
    }
}