首页 > 代码库 > poj-2115-C Looooops-扩展欧几里德

poj-2115-C Looooops-扩展欧几里德

题目大意:

给你A,B,C,K,让你求出一个最小的x使得:

A+C*x=B(mod 2^k)

即C*x=B-A(mod 2^k);

扩展欧几里德的模版题:
对于

A*x=d(mod B)

即A*x+B*y=d d=gcd(A,B);

d=exgcd(A,B,x,y);

那么此时,x的值即为最小的x。

但x有可能为负数,所以最小的正整数解为

x=(x%(B/d)+B/d;


不知道为什么代码不能粘贴上来。。。就不贴代码了。。。。