Description求关于\(x\)的同余方程 \(ax \equiv 1 \pmod {b}\) 的最小正整数解。 Input一行，包含两个正整数 \(a,b\)用一个空格隔开。 Output一个正整数 \(x_0\)即最小正整数解。输入数据保证一定有解。 Solution #include<cstdio> #include<algorithm> #include<cstring> using namespace std; long long a,b,x,y; void exgcd(long long a,long long b,long long &x,long long &y) {if (b==0){x=1;y=0;return;}exgcd(b,a%b,x,y);l...
eg：求5关于模14的乘法逆元15 = 5*2+1 5 = 4*1+1 说明5与14互素，存在5关于14的乘法逆元 1 = 5-4 = 5-（14-5*2）= 5*3-14 因此5关于模14的乘法逆元为3 a存在模b的乘法逆元的充要条件是gcd（a,b）= 1 互质：两个数的最大公约数为1，则称这两个数互质，也叫互素 对于扩展欧几里得算法求乘法逆元的步骤解析。设a>b 显然当b=0,gcd(a,b)=a. 此时x=1，y=0 当b!=0时 设a*x1+b*y1 = gcd(a,b) b*x2+(a mod b)*y2 = gcd(b,a mod b)因为 gcd(...
#include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> #define ll long long #define rep(i,j,k) for(int i=j;i<=k;++i) using namespace std; const int maxx = 1e4+7; ll a[maxx]; void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y) {if (!b){d=a;x=1;y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);} } int main() {int n;while(~scanf("%d",&n)){memset(a,0,sizeof(a));for (int i=1; i<=2*n; i+=2){scanf("%lld...
本篇将附上扩展欧几里得算法的思想与推导;对于一个方程\(a*x+b*y=gcd(a,b)\)来说,我们可以做如下的推导: 设有\(a*x_1+b*y_1=gcd(a,b)\); 同时我们有\(b*x_2+(a\%b)*y_2=gcd(b,a\%b)\); 对于这个方程组,我们希望知道的是\(x_1,x_2,y_1,y_2\)之间的关系,这样我们才可以递归解决这个问题; 我们观察\(b*x_2+(a%b)*y_2\)这个式子,我们可以将\((a\%b)\)写作\((a-\lfloor\frac{a}{b}\rfloor*b)\),将括号打开常数\(a,b\)合并,合并之后的结果...
我们接着上面的欧几里得算法说 扩展欧几里得算法 扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式\(^①\)： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。 ①：裴蜀定理: 裴蜀定理\((Bezouts identity)\)是代数几何中一个定理，其内容是若设a,b是整数，则存在整数x,y，使得ax+by=gcd（a,b），(a,b)代表最大公因数，则设a,b是不全为零的整数，则存在...
度娘百科说： 首先， ax+by = gcd(a, b) 这个公式肯定有解 （( ????? )她说根据数论中的相关定理可以证明，反正我信了） 所以 ax+by = gcd(a, b) * k 也肯定有解 （废话，把x和y乘k倍就好了） 所以，这个公式我们写作ax+by = d，(gcd(a, b) | d) gcd(a, b) | d，表示d能整除gcd，这个符号在数学上经常见 那么已知 a，b 求 一组解 x，y 满足 ax+by = gcd(a, b) 这个公式 1 #include<cstdio>2 typedef long long LL;3 void ext...