双六---扩展欧几里得---挑战编程

感谢http://www.cnblogs.com/oscar-cnblogs/p/6428920.html

题目描述 :一个双六(类似大富翁的桌上游戏)上面有向前 向后无限延续的格子， 每个格子都写有整数。其中0号格子是起点，1号格子是终点。而骰子上只有a,b,-a,-b四个整数，所以根据a和b的值的不同，有可能无法到达终点掷出四个整数各多少次可以到达终点呢？如果解不唯一，输出任意一组即可。如果无解 输出-1

问题就是求 ax+by = c的通解

证明一: 一定存在 x, y 使得 ax+by = k*gcd(a, b) 

 设 a = gcd(a, b)*ra; b = gcd(a, b)*rb;

∵gcd(ra, rb) = 1

∴ax+by = (x*ra+y*rb)*gcd(a, b) = k*gcd(a, b) ----->k = (x*ra+y*rb)

有∵ gcd(ra, rb) = 1 由贝祖定理 一定存在 x, y  (x*ra+y*rb = gcd(ra, rb) = 1)

所以题目中的c = 1

1、那么一定要 a 和b互质 才能得到1

2、ax+by = 1是一个不定方程 

对于求其中的一组特解  可以使用 扩展欧几里得

extgcd(int a, int b, int &x, int &y)

#include

#include

#include

#include

#include

#define READ() freopen("in.txt", "r", stdin);

#define MAXV 2007

#define MAXE 20007

#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

///扩展欧几里得

int extgcd(int a, int b, int &x, int &y)///c++的引用代入 也可以用指针

{

if (b == 0)

{

x = 1;

y = 0;

return a;

}

int ans = extgcd(b, a%b, x, y);

int tmp = x;

x = y;

y = tmp - a/b*y;

return ans;

}

///更简洁的写法 书上的 直接将y传到x的位置 x传到y的位置然后y再-a/b*y

int Extgcd(int a, int b, int &x, int &y)

{

int d = a;

if (b != 0)

{

d = Extgcd(b, a%b, y, x);

y -= a/b*x;

}

else

{

x = 1;

y = 0;

}

return d;

}

int main()

{

//READ()

int a, b, x, y;

int cnt[4] = {0};

scanf("%d%d", &a, &b);

if (extgcd(a, b, x, y) != 1)

{

cout << -1 << endl;

return 0;

}

if (x > 0) cnt[0] = x;

else if (x < 0) cnt[2] = -x;

if (y > 0) cnt[1] = y;

else if (y < 0) cnt[3] = -y;

for (int i = 0; i < 4; i++)

cout << cnt[i];

cout << endl;

return 0;

}

好文链接