poj2115-C Looooops(扩展欧几里德算法)

页面导航:首页 > 软件编程 > C 语言 > poj2115-C Looooops(扩展欧几里德算法)

poj2115-C Looooops(扩展欧几里德算法)

来源:互联网 作者:脚本宝典 时间:2015-09-22 13:27 【

本题和poj1061青蛙问题同属一类,都运用到扩展欧几里德算法,可以参考poj1061,解题思路步骤基本都一样。 一,题意: 对于for(i=A ; i!=B ;i+=C)循环语句,问在k位存储系统中循环几次才会

本题和poj1061青蛙问题同属一类,都运用到扩展欧几里德算法,可以参考poj1061,解题思路步骤基本都一样。
一,题意:
  对于for(i=A ; i!=B ;i+=C)循环语句,问在k位存储系统中循环几次才会结束。
    比如:当k=4时,存储的数 i 在0-15之间循环。(本题默认为无符号)
  若在有限次内结束,则输出循环次数。
  否则输出死循环。
二,思路:
本题利用扩展欧几里德算法求线性同余方程,设循环次数为 x ,则解方程 (A + C*x) % 2^k = B ;求出最小正整数 x。 
  1,化简方程化为求线性同余方程标准式 ax = b (mod n);
  2,扩展欧几里德算法求解线性同余方程 C*x = B-A (mod 2^k);
  3,求出最小非负整数解。
三,步骤:
  1,化简:(A + C*x) mod 2^K = B  -->  C*x mod 2^k = B-A  -->   C*x = B-A (mod 2^k);
  2,求线性同余方程 C*x = B-A (mod 2^k) , 就相当于求二元一次方程 C*x + 2^k * y = B-A 
    i,代入扩展欧几里德算法,求解方程 C*x + 2^k * y = gcd(C , 2^k) ; 
    ii,利用方程 C*x + 2^k * y = gcd(C , 2^k)的解 x0 以及公式 x1 = x0 * c/d 求出原方程 a*x + b*y = c 的解 x1 ;前提是:d|c (c 能被 d 整除);
   3,利用周期性变化求最小的非负整数解 公式: x1 = (x1 % (b/d) + (b/d) ) % (b/d);

    若方程的C*x + 2^k * y = B-A 的一组整数解为(x1 , y1),则它的任意整数解为(x1 + k * (b/d) , y1 - k * (a/d) ) ( k取任意整数 ), T = b/d就为 x1 增长的周期 

     i,若x1为负值,取最大的非正值:x1 = x1 % T ; 若x1为正值,以下两步无影响; 
     ii,取正 :x1 = x1 + T ;
     iii, 防止 i 中的 x1=0 即 ii 中的 x1=T :x1 = x1 % T ;

代码如下:

#include<iostream>
using namespace std;

void exgcd(long long a,long long b,long long& d,long long& x,long long& y){//int& a 是定义一个存放整形变量a的地址
    if(!b){ d=a ; x=1 ; y=0; }              // d用来存储gcd(a,b)的值 
    else { exgcd(b , a%b , d , y , x); y -= x* (a/b); }
}

int main(){
    long long  A,B,C,d,x,y,T;
    int k ; 
    while(cin>>A>>B>>C>>k){
        if(A==0&&B==0&&C==0&&k==0)
             break;
        long long n = 1LL<<k; //n = 1 * 2^k ;注意此处,若为__int64,则应该是n = (__int64)1 << k;
        exgcd(C,n,d,x,y);           
        if( (B-A) % d != 0 ){
            cout<<"FOREVER\n";
        }
        else {
            x = x * (B-A) / d ;  
            T = n / d;
            x = ( x%T + T ) % T ;
            cout<<x<<endl;
        }
    } 
    return 0; 
}


Tags:

相关文章

    文章评论

    最 近 更 新
    热 点 排 行
    Js与CSS工具
    代码转换工具
    
    <