模线性方程

2019-04-13 12:10发布

站内文章 / 模拟电子
15907 0 1559
poj2115 大致题意： 对于C的for(i=A ; i!=B ;i +=C)循环语句，问在k位存储系统中循环几次才会结束。 若在有限次内结束，则输出循环次数。 否则输出死循环。 解题思路：
根据题意可得方程: A+C*X=B （X 再%2^k 就是最后要的结果。） X=[（B-A） / C]% 2^k   =[（B-A） % 2^k] / C  （C 不需要%，因为  (0 <= A, B, C < 2k) ）   =[（B-A）+2^k]%2^k /C CX=[（B-A）+2^k]%2^k     （说明 （B-A）与CX 关于 2^k 同余） 所以  CX - （B-A） 是 2^k 的整数倍  PS：因为两个%它 余数相同的话，，两个相减就把余数减掉了！ 所以得到方程： C*X+Y*2^k=（B-A）    PS：（Y是倍数，X即为所求） 解法就很清晰了！ 先用 exgcd 求出一组解，然后再模一下 求出 最小解就ok了！ FOREVER 的情况就是（B-A）%gcd 不是整数的情况。。即无限循环！！ //Accepted 132K 0MS C++ 646B #include #include using namespace std; typedef long long ll; void exgcd(ll a,ll b,ll& d,ll& x,ll& y) { if(!b){d=a;x=1;y=0;} else{exgcd(b,a%b,d,y,x);y-=x*(a/b);} } ll mod(ll a,ll b,ll n) { ll d,x,y,l; exgcd(a,n,d,x,y); if(b%d!=0) return -1; x*=b/d; l=n/d; x=(x%l+l)%l; return x; } int main() { ll A,B,C,k; while(~scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&k)) { if(A==0&&B==0&&C==0&&k==0) break; ll flag; flag=mod(C,B-A,1LL<

热门文章