caioj 1153 扩展欧几里德算法（解不定方程）

模板题

注意exgcd函数要稍微记一下

#include<cstdio>

#include<cctype>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

void read(int& x)

{

	int f = 1; x = 0; char ch = getchar();

	while(!isdigit(ch)) { if(ch == '-1'); f = -1; ch = getchar(); }

	while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }

	x *= f;

}

void exgcd(int a, int b, int& d, int& x, int& y)

{

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

	else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }

}

int main()

{

   int a, b, c, x, y, d;

   read(a), read(b), read(c);

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

   if(c % d != 0) puts("no solution!");

   else printf("%d %d\b", x * (c / d), y * (c / d));

   return 0;

}

巴特西

caioj 1153 扩展欧几里德算法（解不定方程）

最新文章

热门文章