「NOIP2012」同余方程

题目链接:LOJ 2605

Description

求$ax \equiv 1(\mod b)$的最小正整数解。

Data Range

$2\leq a,b\leq 2000000000$

Solution

将问题转化成$ax+by=c$的模型,我们就可以用扩展欧几里得来计算出一组特殊解,在这里就是最小解。
我们就把原来的式子变成$ax-by=1$的问题,因为题目保证了一定有解,那么就说明两个给定的数一定是互质的。
所以我们就只需要求出这个算式的最小值,然后$\mod b$取最小就可以了。

Code

#include <bits/stdc++.h>

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 g = exgcd(b, a % b, y, x);
  y -= (a / b) * x;
  return g;
}

int main() {
  ll a, b;
  scanf("%lld%lld", &a, &b);
  ll x0, y0;
  ll g = exgcd(a, b, x0, y0);
  printf("%lld\n", ((x0 % b + b) % b));
  return 0; 
}
最后修改:2019 年 09 月 07 日 08 : 07 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论