扩展欧几里得算法模板题 【数学|扩展欧几里得算法模板题】P1082 同余方程
这就是一个有一点小弯的扩展欧几里得的模板题
根据 ax ≡ 1( mod b) 这个方程你应该化简成ax - by = 1 的形式.然后就可以AC了
#include
using namespace std;
#define ll long long int
ll exgcd(ll m, ll n, ll & x, ll & y)
{
if(n==0)
{
x=1;
y=0;
return m;
}
else
{
ll r=exgcd(n,m%n,x,y);
ll temp=y;
y=x-(m/n)*y;
x=temp;
return r;
}
}
int main()
{
ll a,b,c,d,e,f;
ll x,y;
cin>>a>>b;
c=exgcd(a,b,x,y);
/// 这里求得c是最大公约数，因为刚刚给的方程ax - by = 1 如果存在x、y的值的话c就一定是互质的
/// 这里题目给的是一定存在，所以c的值就一定为1。所以这里看你们心情加就行了。
if(c==1)
{
if(x<0)
while(x<0)
x+=abs(b);
else
{
while(x>0)
x-=abs(b);
x+=abs(b);
}
cout<=0)
//x=x%t;
//else
//x=x%t+t;
//cout< 因为最后题目要求是求出x的最小的非零值，所以我们有这么个结论：
ax+by=1
a x + b y + k × b a ? k × b a = 1
a ( x + k b ) + ( y ? k a) b = 1
所以我们知道在x的后面加上k倍的b和y的后面同时减去k倍的a这个等式依旧成立，
所以根据这对结果进行简单处理一下就成了。
推荐阅读
- AIoT(人工智能+物联网)|程序员的数学【线性代数基础】
- topcoder|Topcoder SRM 661 Div1 Easy: MissingLCM
- HDU 5184 Brackets (卡特兰数)
- 高斯消元
- 水题纪念|【51nod - 1098】 最小方差（基础数学，公式化简，前缀和，积的前缀和）
- 扩展欧几里德算法（gcd扩展使用）
- 数学|CF 514D.Nature Reserve 几何,二分,交集
- codeforces|Codeforces Round #665 (Div. 2) C. Mere Array(数学)
- codeforces|Codeforces Round #665 (Div. 2) A. Distance and Axis(思维，数学)
- 数论|Codeforces Global Round 10 B. Omkar and Infinity Clock(数学)