洛谷 P1082 同余方程题解

每日一题 day31 打卡

Analysis

题目问的是满足 ax mod b = 1 的最小正整数 x。（a,b是正整数）

但是不能暴力枚举 x，会超时。

把问题转化一下。观察 ax mod b = 1，它的实质是 ax + by = 1：这里 y 是我们新引入的某个整数，并且似乎是个负数才对。这样表示是为了用扩展欧几里得算法。我们将要努力求出一组 x,y 来满足这个等式。稍微再等一下——

问题还需要转化。扩展欧几里得是用来求 ax + by = gcd(a,b) 中的未知数的，怎么牵扯到等于 1 呢？

原理是，方程 ax + by = m 有解的必要条件是 m mod gcd(a,b) = 0

这个简单证一下。

由最大公因数的定义，可知 a 是 gcd(a,b) 的倍数，且 b 是 gcd(a,b) 的倍数，

若 x,y 都是整数，就确定了 ax + by 是 gcd(a,b) 的倍数，

因为 m = ax + by，所以 m 必须是 gcd(a,b) 的倍数，

那么 m mod gcd(a,b) = 0

可得出在这道题中，方程 ax + by = 1 的有解的必要条件是 1 mod gcd(a,b) = 0，可怜的 gcd(a,b) 只能等于 1 了。这实际上就是 a,b 互质。

然后就可以直接套拓欧的板子了.

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int a,b,x,y;

 inline void exgcd(int a,int b)

 {

     if(b==)

     {

         x=;

         y=;

         return;

     }

     exgcd(b,a%b);

     int re_x=x;

     x=y;

     y=re_x-a/b*y;

 }

 signed main()

 {

     a=read();b=read();

     exgcd(a,b);

     x=(x%b+b)%b;

     write(x);

     return ;

 }

请各位大佬斧正~~（反正我不认识斧正是什么意思）~~

巴特西

洛谷 P1082 同余方程题解

Analysis

最新文章

热门文章

巴特西

洛谷 P1082 同余方程 题解

Analysis

最新文章

热门文章

洛谷 P1082 同余方程题解