POJ - 2115 C Looooops（扩展欧几里德求解模线性方程（线性同余方程））

d.对于这个循环，

for (variable = A; variable != B; variable += C)


 statement;

给出A，B，C，求在k位存储系统下的循环次数。

例如k=4时，变量variable则只在0~15之间循环变化。

s.扩展欧几里德求解模线性方程（线性同余方程）。

设循环次数为x，

1.(A+C*x)mod 2^k=B. --> C*x=B-A(mod 2^k). （怎么变来的？）

2.C*x=B-A(mod 2^k). --> C*x+(2^k)*y=B-A.

扩展欧几里德求：C*x+(2^k)*y=gcd(C,2^k)=d.（原式：a*x+b*y=gcd(a,b)=d，以下a代表C，b代表2^k。）

如果(B-A)mod d==0（也就是(B-A)的值可以整除d，貌似表示为d|(B-A)？），则原方程C*x+(2^k)*y=B-A.的解为x'=x*((B-A)/d)。

3.利用周期性变化，求出最小的非负整数解为x''=(x'%(b/d)+(b/d))%(b/d).

因为：如果C*x+(2^k)*y=B-A.的一组整数解为(x1,y1)，则它的任意整数解为(x1+k*(b/d)),y1-k*(a/d)).(k取任意整数)

（1）x'%(b/d)，使解在(-b/d,b/d)

（2）+(b/d)，使解在(0,2*b/d)

（3）%(b/d)，得到最小整数解

为什么b/gcd(a,b)，a/gcd(a,b)分别为x，y的解的最小间距？

解：假设c为x的解的最小间距，此时d为y的解的间距，所以x=x0+c*t，y=y0-d*t（x0，y0为一组特解，t为任意整数）

带入方程得：a*x0+a*c*t+b*y0-b*d*t=n,因为a*x0+b*y0=n，所以a*c*t-b*d*t=0，t不等于0时，a*c=b*d

因为a,b,c,d都为正整数，所以用最小的c，d，使得等式成立，ac，bd就应该等于a，b的最小公倍数a*b/gcd(a,b),

所以c=b/gcd(a,b)，d就等于a/gcd(a,b)。

若最后所求解要求x为最小整数，那么x=(x0%（b/gcd(a,b))+b/gcd(a,b))%(b/gcd(a,b))即为x的最小整数解。

x0%（b/gcd(a,b))使解落到区间-b/gcd(a,b)~b/gcd(a,b)，再加上b/gcd(a,b)使解在区间0~2*b/gcd(a,b)，

再模上b/gcd(a,b)，则得到最小整数解（注意b/gcd(a,b)为解的最小距离，重要）

#include<iostream>

#include<stdio.h>

using namespace std;

//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y

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

    if(a==&&b==)return -;//无最大公约数

    if(b==){x=;y=;return a;}

    long long d=extend_gcd(b,a%b,y,x);

    y-=a/b*x;

    return d;

}

//求逆元

//ax=1(mod n)

long long mod_reverse(long long a,long long n){

    long long x,y;

    long long d=extend_gcd(a,n,x,y);

    if(d==)return (x%n+n)%n;

    else return -;

}

int main(){

    long long A,B,C,k;

    long long a,b,x,y;

    long long d;

    while(~scanf("%lld%lld%lld%lld",&A,&B,&C,&k)){

        if(A==&&B==&&C==&&k==)break;

        a=C;

        b=((long long))<<k;

        d=extend_gcd(a,b,x,y);

        if((B-A)%d==){

            x=(x*((B-A)/d))%b;

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

            printf("%lld\n",x);

        }

        else{

            printf("FOREVER\n");

        }

    }

    return ;

}

ps:题解可以参考这个：http://www.cnblogs.com/My-Sunshine/p/4828600.html 当时就是看这个才懂的

巴特西

POJ - 2115 C Looooops（扩展欧几里德求解模线性方程（线性同余方程））

最新文章

热门文章