• <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>

            Google code jam 2008 R1A - Numbers

            Problem

            In this problem, you have to find the last three digits before the decimal point for the number (3 + √5)n.

            For example, when n = 5, (3 + √5)5 = 3935.73982... The answer is 935.

            For n = 2, (3 + √5)2 = 27.4164079... The answer is 027.

            Input

            The first line of input gives the number of cases, T. T test cases follow, each on a separate line. Each test case contains one positive integer n.

            Output

            For each input case, you should output:

            Case #X: Y
            where X is the number of the test case and Y is the last three integer digits of the number (3 + √5)n. In case that number has fewer than three integer digits, add leading zeros so that your output contains exactly three digits.

             

            Limits

            1 <= T <= 100

            Small dataset

            2 <= n <= 30

            Large dataset

            2 <= n <= 2000000000

            Sample


            Input
             

            Output
             
            2
            5
            2
            Case #1: 935
            Case #2: 027


            Analysis

            This problem with a simple statement was in fact one of the hardest in Round 1. The input restrictions for the small input were chosen so that straightforward solutions in Java or Python, which have arbitrary-precision numbers, would fail. The trick was calculating √5 to a large enough precision and not using the default double value. It turned out that using the Windows calculator or the UNIX bc tool was enough to solve the small tests as well.

            Solving the large tests was a very different problem. The difficulty comes from the fact that √5 is irrational and for n close to 2000000000 you would need a lot of precision and a lot of time if you wanted to use the naive solution.

            The key in solving the problem is a mathematical concept called conjugation. In our problem, we simply note that (3 - √5) is a nice conjugate for (3 + √5). Let us define

            (1)     α := 3 + √5,   β := 3 - √5,   and Xn := αn + βn.
            We first note that Xn is an integer. This can be proved by using the binomial expansion. If you write everything down you'll notice that the irrational terms of the sums cancel each other out.
            (2)    
            Another observation is that βn < 1, so Xn is actually the first integer greater than αn. Thus we may just focus on computing the last three digits of X.

             

            A side note. In fact, βn tends to 0 so quickly that that our problem would be trivial if we asked for the three digits after the decimal point. For all large values of n they are always 999.

            Based on (1) and (2), there are many different solutions for finding the last three digits of Xn.

            Solution A. [the interleave of rational and irrational]

            One solution goes like this: αn can be written as (an + bn√5), where an and bn are integers. At the same time, βn is exactly (an - bn√5) and Xn = 2an. Observe that

            (3)     α(n + 1) = (3 + √5)(an + bn√5) = (3an + 5bn) + (3bn + an)√5.
            So an + 1 = 3an + 5bn and bn + 1 = 3bn + an. This can be written in matrix form as
            (4)    
            Since α0 = 1, we have (a0, b0) = (1, 0).

             

            Now we use the standard fast exponentiation to get An in O(log n) time. Note that we do all operations modulo 1000 because we just need to return the last three digits of an.

            Here's some Python code that implements this solution:

            def matrix_mult(A, B):
            C = [[0, 0], [0, 0]]
            for i in range(2):
            for j in range(2):
            for k in range(2):
            C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % 1000
            return C
            def fast_exponentiation(A, n):
            if n == 1:
            return A
            else:
            if n % 2 == 0:
            A1 = fast_exponentiation(A, n/2)
            return matrix_mult(A1, A1)
            else:
            return matrix_mult(A, fast_exponentiation(A, n - 1))
            def solve(n):
            A = [[3, 5], [1, 3]]
            A_n = fast_exponentiation(A, n)
            return (2 * M_n[0][0] + 999) % 1000
            

             

            Solution B. [the quadratic equation and linear recurrence]

            Experienced contestants may notice there is a linear recurrence on the Xi's. Indeed, this is not hard to find -- the conjugation enters the picture again.

            Notice that

            (5)     α + β = 6, and α β = 4.
            So α and β are the two roots of the quadratic equation x2 - 6x + 4 = 0. i.e.,
            (6)     α2 = 6α - 4, and β2 = 6β - 4.
            Looking at (1) and (6) together, we happily get
            (7)     Xn+2 = 6Xn+1 - 4Xn.
            Such recurrence can always be written in matrix form. It is somewhat redundant, but it is useful:
            From here it is another fast matrix exponentiation. Let us see radeye's perl code that implements this approach here:
            sub mul {
            my $a = shift ;
            my $b = shift ;
            my @a = @{$a} ;
            my @b = @{$b} ;
            my @c = ($a[0]*$b[0] + $a[1]*$b[2],
            $a[0]*$b[1] + $a[1]*$b[3],
            $a[2]*$b[0] + $a[3]*$b[2],
            $a[2]*$b[1] + $a[3]*$b[3]) ;
            @c = map { $_ % 1000 } @c ;
            return @c ;
            }
            sub f {
            my $n = shift ;
            return 2 if $n == 0 ;
            return 6 if $n == 1 ;
            return 28 if $n == 2 ;
            $n -= 2 ;
            my @mat = (0, 1, 996, 6) ;
            my @smat = @mat ;
            while ($n > 0) {
            if ($n & 1) {
            @mat = mul([@mat], [@smat]) ;
            }
            @smat = mul([@smat], [@smat]) ;
            $n >>= 1 ;
            }
            return ($mat[0] * 6 + $mat[1] * 28) % 1000 ;
            }
            sub ff {
            my $r = shift ;
            $r = ($r + 999) % 1000 ;
            $r = "0" . $r while length($r) < 3 ;
            return $r ;
            }
            for $c (1..<>) {
            $n = <> ;
            print "Case #$c: ", ff(f($n)), "\n" ;
            }
            

             

            Solution C. [the periodicity of 3 digits]

            For this problem, we have another approach based on the recurrence (7). Notice that we only need to focus on the last 3 digits of Xn, which only depends on the last 3 digits of the previous two terms. The numbers eventually become periodic as soon as we have (Xi, Xi+1) and (Xj, Xj+1) with the same last 3 digits, where i < j. It is clear that we will enter a cycle no later than 106 steps. In fact, for this problem, you can write some code and find out that the cycle has the size 100 and starts at the 3rd element in the sequence. So to solve the problem we can just brute force the results for the first 103 numbers and if n is bigger than 103 return the result computed for the number (n - 3) % 100 + 3.

            Solution D. [the pure quest of numbers and combinatorics]

            Let us see one more solution of different flavor. Here is a solution not as general as the others, but tailored to this problem, and makes one feel we are almost solving this problem by hand.

            Let us look again at (2). We want to know Xn mod 1000. We know from the chinese remander theorem that if we can find Xn mod 8 and Xn mod 125, then Xn mod 1000 is uniquely determined.
            (a) For n > 2, Xn mod 8 is always 0. Since 5i ≡ 1 (mod 4), 3n-2i ≡ 1 or -1 (mod 4) depending on n, so, for n > 2,
            (b) To compute Xn mod 125, we only need to worry about i=0,1,2. All the rest are 0 mod 125. In other words, all we need to compute is
            There are various ways to compute the elements in the above quantity. The exponents can be computed by fast exponentiation, or using the fact that 3n mod 125 is periodic with cycle length at most 124. The binomial numbers can be computed using arbitrary precision integers in languages like Java and Python, or with a bit careful programming in languages like C++.

             

            Afterword

            There were many other interesting solutions submitted by the contestants, and Nathan Collins actually went through many of them and tried to summarize them in his awesome blog post.

            More information:

            Binomial numbers - Linear recurrence - Exponentiation - Chinese remainder theorem


            Source Code
            #include <iostream>

            using namespace std;

            #define Rep(i,n) for (int i(0),_n(n); i<_n; ++i)

            int* matrix_mult(int* A, int* B, int* ret) {
                Rep(i,
            2{
                    Rep(j,
            2{
                        Rep(k,
            2{
                            ret[i
            *2+k] = (ret[i*2+k] + A[i*2+j] * B[j*2+k]) % 1000;
                        }

                    }

                }

                
            return ret;
            }


            int* fast_exponentiation(int* A, int n, int* A1) {
                
            if (n == 1{
                    Rep(i,
            4{
                        A1[i] 
            = A[i];
                    }

                    
            return A1;
                }

                
            else if (n % 2 == 0{
                    
            int A_tmp[] = {0,0,0,0};
                    fast_exponentiation(A, n
            /2, A_tmp);
                    matrix_mult(A_tmp, A_tmp, A1);
                    
            return A1;
                }

                
            else {
                    
            int A_tmp[] = {0,0,0,0};
                    fast_exponentiation(A, n 
            - 1, A_tmp);
                    matrix_mult(A, A_tmp, A1);
                    
            return A1;
                }

            }


            int solve(int n) {
                
            int A[] = {3513};
                
            int ret[] = {0,0,0,0};
                fast_exponentiation(A, n, ret);
                
            return (2 * ret[0+ 999% 1000;
            }



            int main()
            {
                
            int T;
                scanf(
            "%d"&T);
                Rep(t, T) 
            {
                    
            int n;
                    scanf(
            "%d"&n);
                    
            int ret = solve(n);
                    
                    printf(
            "Case #%d: %03d\n", t+1, ret);
                }

            }

            posted on 2009-08-12 21:19 Chauncey 閱讀(588) 評論(0)  編輯 收藏 引用


            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            導(dǎo)航

            <2009年8月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            統(tǒng)計

            常用鏈接

            留言簿

            隨筆檔案(4)

            文章檔案(3)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            九九久久精品国产| 久久久久国产一级毛片高清版| 国产亚州精品女人久久久久久| 精品久久久久一区二区三区| 欧美精品福利视频一区二区三区久久久精品 | 久久棈精品久久久久久噜噜| 国产婷婷成人久久Av免费高清| 天天综合久久久网| 国产美女亚洲精品久久久综合 | 久久超碰97人人做人人爱| 久久精品国产久精国产| 伊人久久大香线蕉无码麻豆| 午夜不卡久久精品无码免费| 亚洲一区中文字幕久久| 亚洲va久久久噜噜噜久久狠狠| A级毛片无码久久精品免费| 国产成年无码久久久免费| 成人精品一区二区久久久| 亚洲成色www久久网站夜月| 久久精品国产精品亚洲| 国产成年无码久久久久毛片 | 人妻少妇久久中文字幕| 久久久久国产| 亚洲国产精品久久66| 久久人妻少妇嫩草AV无码专区| 久久中文字幕视频、最近更新| 香蕉久久夜色精品国产小说| 国产美女久久久| 久久久无码人妻精品无码| 思思久久99热只有频精品66| 久久国产精品成人免费| 久久不见久久见免费视频7| 成人久久免费网站| 午夜天堂精品久久久久| 人妻精品久久无码专区精东影业 | 久久福利青草精品资源站免费| 久久丫精品国产亚洲av不卡| 亚洲成色www久久网站夜月| 欧美亚洲色综久久精品国产| 天天爽天天狠久久久综合麻豆| 亚洲精品无码久久久久|