• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            POJ 2115 模線性方程 ax=b(mod n)

            Description

            A Compiler Mystery: We are given a C-language style for loop of type
            for (variable = A; variable != B; variable += C)
            
            statement;

            I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats statement followed by increasing the variable by C. We want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a k-bit unsigned integer type (with values 0 <= x < 2k) modulo 2k.

            Input

            The input consists of several instances. Each instance is described by a single line with four integers A, B, C, k separated by a single space. The integer k (1 <= k <= 32) is the number of bits of the control variable of the loop and A, B, C (0 <= A, B, C < 2k) are the parameters of the loop.

            The input is finished by a line containing four zeros.

            Output

            The output consists of several lines corresponding to the instances on the input. The i-th line contains either the number of executions of the statement in the i-th instance (a single integer number) or the word FOREVER if the loop does not terminate.

            Sample Input

            3 3 2 16
            3 7 2 16
            7 3 2 16
            3 4 2 16
            0 0 0 0
            

            Sample Output

            0
            2
            32766
            FOREVER

            Source


                推論1:方程ax=b(mod n)對(duì)于未知量x有解,當(dāng)且僅當(dāng)gcd(a,n) | b。
                推論2:方程ax=b(mod n)或者對(duì)模n有d個(gè)不同的解,其中d=gcd(a,n),或者無解。
                定理1:設(shè)d=gcd(a,n),假定對(duì)整數(shù)x和y滿足d=ax+by(比如用擴(kuò)展Euclid算法求出的一組解)。如果d | b,則方程ax=b(mod n)有一個(gè)解x0滿足x0=x*(b/d) mod n 。特別的設(shè)e=x0+n,方程ax=b(mod n)的最小整數(shù)解x1=e mod (n/d),最大整數(shù)解x2=x1+(d-1)*(n/d)。
                定理2:假設(shè)方程ax=b(mod n)有解,且x0是方程的任意一個(gè)解,則該方程對(duì)模n恰有d個(gè)不同的解(d=gcd(a,n)),分別為:xi=x0+i*(n/d) mod n 。
                以上定理的具體證明見《算法導(dǎo)論》。
            #include <iostream>
            using namespace std;

            long long ext_gcd(long long a,long long b,long long &x,long long &y){
                
            long long t,ret;
                
            if(!b){
                    x
            =1,y=0;
                    
            return a;
                }

                ret
            =ext_gcd(b,a%b,x,y);
                t
            =x,x=y,y=t-a/b*y;
                
            return ret;
            }

            long long modular_linear(long long a,long long b,long long n){
                
            long long d,e,x,y;
                d
            =ext_gcd(a,n,x,y);
                
            if(b%d)
                    
            return -1;
                e
            =x*(b/d)%n+n;
                
            return e%(n/d);
            }

            int main(){
                
            long long d,a,b,c,k;
                
            while(scanf("%lld %lld %lld %lld",&a,&b,&c,&k),a||b||c||k){
                    d
            =modular_linear(c,b-a,1LL<<k);
                    
            if(d==-1)
                        puts(
            "FOREVER");
                    
            else
                        printf(
            "%lld\n",d);
                }

                
            return 0;
            }

            posted on 2009-06-12 19:24 極限定律 閱讀(2668) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久久噜噜噜久久中文字幕色伊伊| 99久久精品国产高清一区二区| 欧美粉嫩小泬久久久久久久 | 77777亚洲午夜久久多喷| 亚洲色欲久久久综合网东京热| 精品久久久久久| 亚洲精品成人网久久久久久| 久久人爽人人爽人人片AV | 久久99国产综合精品女同| 日韩欧美亚洲综合久久影院d3| 久久亚洲精品无码观看不卡| 亚洲午夜无码久久久久| 国产精品久久久久久久久久免费| 亚洲国产视频久久| 久久久久九九精品影院| av午夜福利一片免费看久久| 精品久久久一二三区| 久久人人爽人人精品视频| 久久人人爽人人爽人人片AV不 | 亚洲美日韩Av中文字幕无码久久久妻妇 | 97超级碰碰碰碰久久久久| 天天爽天天狠久久久综合麻豆| 久久精品国产清自在天天线| 97超级碰碰碰久久久久| 中文字幕久久波多野结衣av| 久久丝袜精品中文字幕| 欧美亚洲另类久久综合| 久久精品国产久精国产| 国内精品久久久久影院优| 一级女性全黄久久生活片免费| 久久久久国产一级毛片高清板 | 91久久精品91久久性色| 久久国产亚洲精品| 久久亚洲国产精品成人AV秋霞| 日本精品久久久久影院日本| 国产精品成人99久久久久 | 久久精品国产一区二区| 久久久久人妻一区精品| 久久影视综合亚洲| 欧美成人免费观看久久| 成人久久免费网站|