POJ 2115--C Looooops

2019-04-13 22:13发布

站内文章 / 模拟电子
9897 0 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，则有解。
  1. 根据gcd定理：设d = C*x+n*y，其中x,y为整数，(d,x,y)都可以由欧几里得算法求出。
  2. 设x0 = x*(b/d)，因为mod(C*x0,n) = mod(C*x*(b/d),n) = mod(d*(b/d),n) = b，所以x0就是方程的一个解。
  3. 令xi = x0+i*(n/d)，i为任意整数。因为d也是C的约数，所以mod(xi*C,n) = b。所以xi也是方程的解。且根据算法导论第三版推论31.22，这些解也即是方程的所有解。
  4. 因为方程的解的周期为n/d，所以在[0，n/d)之间有且仅有一解，设此解为x_min，也即是我们要求的解。根据周期性，xi也可以表示为x_min+i*(n/d)，易知mod(xi，n/d)=x_min。因为C里面负数对正数求模仍为非正，所以求模以后需要再加上n/d再求模。

#include long long d,x0,x,y; int extended_euclid(long long a,long long b) { long long tmp_x; if(b == 0) { d = a; x = 1; y = 0; return 0; } extended_euclid(b,a%b); //gcd(a,b) = gcd(b,mod(a,b)); tmp_x = x; x = y; //x = y' y = tmp_x - (a/b)*y; //y = x'-(a/b)*y' return 0; } int main() { long long A,B,C,k; long long n,b; while(scanf("%lld%lld%lld%lld",&A,&B,&C,&k)&&(A|B|C|k)) { n = 1LL<

热门文章