欧几里得定理（nyoj775）
A了一道题目，深入学习了一下欧几里得定理，记录一下：
我们平常了解的欧几里得定理就是求两个数最大公约数。
求最大公约数的定理是：设a，b是任意两个正整数，则gcd（a，b）=Rn，其中Rn是广义欧几里得除法中最后一个非零余数。算法描述
int gcd(int x,int y){ int t=x%y; while(t) { x=y; y=t; t=x%y; } return y;}但是当你遇上一个这样一个问题该怎样快速解决呢？
对于任意两个正整数a和b，必定存在一对整数s、t使得sa+tb=gcd(a,b)。
给出a，b，求s，t。定理：设a，b为任意两个正整数，则Sn*a+Tn*b==gcd（a，b），对于n=0,1,2...这里的Sn，Tn可归纳S0=1,S1=0, S（j）=S（j-2）-q（j-1）*S（j-1）...T0=0,T1=1, T(j)=T(j-2) - q(j-1)*S(j-1) 由此可求出s和t。题目描述：http://acm.nyist.net/JudgeOnline/problem.php?pid=775代码：