洛谷 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 互质。

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define int long long
 6 using namespace std;
 7 inline int read() 
 8 {
 9     int x=0;
10     bool f=1;
11     char c=getchar();
12     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
13     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
14     if(f) return x;
15     return 0-x;
16 }
17 inline void write(int x)
18 {
19     if(x<0){putchar('-');x=-x;}
20     if(x>9)write(x/10);
21     putchar(x%10+'0');
22 }
23 int a,b,x,y;
24 inline void exgcd(int a,int b)
25 {
26     if(b==0)
27     {
28         x=1;
29         y=0;
30         return;
31     }
32     exgcd(b,a%b);
33     int re_x=x;
34     x=y;
35     y=re_x-a/b*y;
36 }
37 signed main()
38 {
39     a=read();b=read();
40     exgcd(a,b);
41     x=(x%b+b)%b;
42     write(x);
43     return 0;
44 }

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

洛谷 P1082 同余方程 题解

Analysis

洛谷 P1082 同余方程题解