洛谷 P1082 同余方程（算法竞赛进阶指南，扩展欧几里得， 线性同余方程）

算法竞赛进阶指南，153页，扩展欧几里得， 线性同余方程

本题要点：
1、同余方程 a * x = 1(mod m), 转化为 方程 a * x + b * y = 1, 利用 扩展欧几里得算法，
求出一组特解，x0 和 y0， x0 就是原来同余方程的一个解， 但是要求最小的正整数解，
只需要把 x0 同余模 到 1 ~ b 的范围内。
2、避免麻烦，直接 long long

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;ll exgcd(ll a, ll b, ll& x, ll& y)
{
    if(!b){
    x = 1, y = 0;return a;}ll d = exgcd(b, a % b, x, y);ll z = x; x = y; y = z - y * (a / b);return d;
}int main()
{
    ll a, b, x, y, ans = 0;scanf("%lld%lld", &a, &b);exgcd(a, b, x, y);while(x < 0){
    x += b;}ans = x % b;printf("%lld\n", ans);return 0;
}/* 3 10 *//* 7 */