例题 双六游戏

一个双六上面有向前 向后无限延续的格子， 每个格子都写有整数。其中0号格子是起点，1号格子

是终点。而骰子上只有a,b,-a,-b四个整数，所以根据a和b的值的不同，有可能无法到达终点

掷出四个整数各多少次可以到达终点呢？如果解不唯一，输出任意一组即可。如果无解 输出impossible！

可将此题转化成ax+by=1的形式

我们使用和辗转相除法相似的思路，将extgcd(a,b,x,y)不断递归为extgcd(b,a%b,x,y),但同时我们要响应得更改x和y，即将x转化为上一次地规避的y，y转化为上一次递归的x-(a/b)*y。

具体证明请自行百度

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

int gcd(int a,int b)

{     if(a<b)swap(a,b);

      if(a%b==0)return b;

      return gcd(b,a%b);

}

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

{     if(b==0){

         x=1;

         y=0;

         return;

      }

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

      int z=x;

      x=y;

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

}

int main()

{     int a,b,x,y,i,j,k;

      cin>>a>>b;

      if(gcd(a,b)!=1)puts("impossible!");

      exgcd(a,b,x,y);

      cout<<x<<' '<<y<<endl;

      return 0;

}