POJ 2115--C Looooops

• qq_26598817 发布于
• 1727 收藏

本题为模线性方程经典题目。 根据题意及同余模定理可以很容易得到模线性方程：mod(x*C,2^k) = mod(B-A+2^k,2^k)，求最小的x。 参考算法导论第三版31章，设n = 2^k，b = mod(B-A+2^k,2^k)，d = gcd(n,C) 。若mod(b,d) = 0，则有解。 根据gcd定理：设d = C*x+n*y，其中x,y为整数，(d,x,y)都可以由欧几里得算法...