3314 扩展gcd

题目描述

输入

输出

示例输入

2 3

示例输出

2

提示

 扩展欧几里德算法是用来在已知a, b求解一组x，y使得a*x+b*y=Gcd(a,b)
(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<map>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;y=0;
		return a;
	}
	else
	{
	   int r=exgcd(b,a%b,x,y);
	   int t=x;
	   x=y;
	   y=t-(a/b)*y;
	   return r;
	}
}
int main()
{
	int n,m;
    while(~scanf("%d%d",&n,&m))
    {
    	int x,y,gcd;
		gcd = exgcd(n,m,x,y);
        x = x*1/gcd;
        x = (x%(m/gcd)+(m/gcd))%(m/gcd);
		printf("%d\n",x);
    }
}

3314 扩展gcd

原文：http://blog.csdn.net/became_a_wolf/article/details/48129705