方程"/>
【洛谷P1082】同余方程
题目大意:求关于 \(x\) 的同余方程 \[ax \equiv 1 \pmod {b}\] 的最小正整数解。
题解:exgcd 板子题。
代码如下
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;ll a,b;ll exgcd(ll a,ll b,ll &x,ll &y){if(!b)return x=1,y=0,a;ll d=exgcd(b,a%b,x,y);ll z=x;x=y,y=z-a/b*y;return d;
}int main(){scanf("%lld%lld",&a,&b);ll x,y;exgcd(a,b,x,y);printf("%lld\n",(x%b+b)%b);return 0;
}
转载于:.html
更多推荐
【洛谷P1082】同余方程
发布评论