如果有相应的OJ题目,欢迎同学们提供相应的链接

相关链接

• 所有模板的快速链接
• 单变元模线性方程模板
• poj_2115_C Looooops,my_ac_code

简单的测试

None

代码模板

/*

 * TIME COMPLEXITY:O(logN)

 * PARAMS:

 *      a

 *      b

 *      x

 *      y

 *

 * ax+by=gcd(a,b)

 * gcd(a,b)=gcd(b,a%b)

 * ax+by=gcd(a,b),bx'+a%by'=gcd(b,a%b)=bx'+(a-a/b*b)y'=ay'+b(x'-a/by')

 * x=y' y=x'-a/by'

 */

int extend_gcd(int a,int b,int &x,int &y){

    if(b==0){

        x=1,y=0;

        return a;

    }else{

        int r=extend_gcd(b,a%b,y,x);//skill. x=y' y=x'-a/by' ==> x=x' y=y'-a/bx'

        y-=a/b*x;

        return r;

    }

}