Warning: session_start(): open(/tmp/sess_3cb7f67c8b9f1d94334d020c1e95abf3, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
2020-2021:teams:farmer_john:2sozx:数学:exgcd

目录

扩展欧几里得

用途

解裴蜀方程

写法

通过普通的欧几里得算法来求解

code

code 

int exgcd(int a, int b, int& x, int& y){
	if(!b) {y=0,x=1;return a;}
	int gcd=exgcd(b,a%b,y,x); 
	y-=a/b*x;
	return gcd;
}