• <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精品国产99久久| 国产午夜精品久久久久九九电影| 亚洲午夜久久久| 一本色道久久综合| 好久久免费视频高清| 国内精品伊人久久久久网站| 久久人人爽人人爽人人片AV麻豆 | 久久午夜福利电影| 久久SE精品一区二区| 久久亚洲精品中文字幕三区| 欧美精品九九99久久在观看| 国产精品久久久久jk制服| 久久久黄片| 久久久久国产一级毛片高清版| 18岁日韩内射颜射午夜久久成人| 日本精品久久久久中文字幕8 | 色综合久久天天综合| 久久精品中文字幕有码| 久久精品人人做人人妻人人玩| 久久精品国产精品亚洲人人| 精品久久久久久无码中文字幕一区| 久久精品成人免费观看97| 丁香色欲久久久久久综合网| 欧美国产成人久久精品| 免费精品99久久国产综合精品| 无遮挡粉嫩小泬久久久久久久| 狠狠色丁香久久婷婷综合图片| 国产激情久久久久影院老熟女免费 | 国产A级毛片久久久精品毛片| 天堂无码久久综合东京热| 国产午夜电影久久| 久久久久久一区国产精品| 久久99精品国产麻豆婷婷| 99热成人精品免费久久| 精品久久久久久99人妻| 久久996热精品xxxx| 久久午夜综合久久| 亚洲欧美国产日韩综合久久| 久久91精品国产91久| 中文国产成人精品久久不卡| 亚洲午夜久久久久久久久电影网|