luogu P1082 同余方程 |扩展欧几里得

2024-08-31 22:21:47

题目描述

求关于 x的同余方程 ax≡1(modb) 的最小正整数解。

输入格式

一行，包含两个正整数 a,ba,b，用一个空格隔开。

输出格式

一个正整数 x，即最小正整数解。输入数据保证一定有解。

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

inline int exgcd(int a,int b,int &x,int &y){

	if(b==0){ x=1; y=0; return a; }

	exgcd(b,a%b,x,y);

	int z=x; x=y; y=z-y*(a/b);

}

signed main(){

	int a,b,x,y; cin>>a>>b;

	exgcd(a,b,x,y);

	while(x<0)x+=b;

	x%=b;

	cout<<x<<endl;

}

最新文章

热门文章