Luogu P1082 同余方程

　　怎么说呢，想通了就是一道模板题了。

　　自己的数论也很烂，但竟然没有看题解搞了过去（奇迹）.

　　首先对于ax ≡ 1 (mod b)； 观察数据范围可以发现b≥2，所以转化成 ax mod b=1

　　从mod的定义中我们可以看出原方程就是ax-by=1（y是整数）

　　因为一定有解，然后由裴蜀定理可以知道gcd(a,b)|1，即gcd(a,b)=1，得证a,b互质。

　　然后就可以套扩欧模板了。

　　CODE

#include<cstdio>
using namespace std;
typedef long long LL;
LL a,b,x,y;
inline void read(LL &x)
{
    x=0; char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline void exgcd(LL a,LL b,LL &x,LL &y)
{
    if (!b) { x=1; y=0; return; }
    exgcd(b,a%b,y,x);
    y-=(a/b)*x;
}
int main()
{
    read(a); read(b);
    exgcd(a,b,x,y);
    printf("%lld",(x%b+b)%b);
    return 0;
}

　　由于扩欧的结果只满足|x|+|y|最小，由题目的要求x为正整数应该输出(x%b+b)%b。