[NOIP 2012 提高组] 同余方程

知识点

扩展欧几里得、乘法逆元

解题思路

由ax≡1(mod b)可得ax+by=1。输入保证有解，即gcd(a,b)=1，使用扩展欧几里得求一组x，再将x规范到[0,b-1]即可。由于b≥2且逆元非0，该值就是最小正解。

正确性说明

扩展欧几里得返回满足ax+by=gcd(a,b)的整数系数。有解保证右侧为1，故x是逆元；所有解对b同余，取最小非负余数并且该余数非0，就得到最小正整数解。

易错点

不能仅用费马小定理，因为模数不保证为质数；扩展系数用64位；负数取模后再加b。

复杂度

时间O(log min(a,b))，递归空间同阶。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
long long ex(long long a,long long b,long long&x,long long&y){if(!b){x=1;y=0;return a;}long long u,v,g=ex(b,a%b,u,v);x=v;y=u-a/b*v;return g;}int main(){long long a,b,x,y;cin>>a>>b;ex(a,b,x,y);cout<<(x%b+b)%b<<'\n';}