青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(593) 評(píng)論(0)  編輯 收藏 引用


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


導(dǎo)航

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

統(tǒng)計(jì)

常用鏈接

留言簿

隨筆檔案(4)

文章檔案(3)

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            免费成人在线观看视频| 欧美黄色成人网| 国产一区二区三区成人欧美日韩在线观看 | 亚洲欧美日韩一区在线| 国产精品色网| 久久在线免费观看视频| 久久久欧美一区二区| 91久久亚洲| 在线亚洲激情| 伊人激情综合| 亚洲精品乱码久久久久久日本蜜臀| 欧美激情精品| 欧美亚洲一级| 蜜桃av一区二区| 亚洲综合色网站| 久久精品国产亚洲高清剧情介绍| 亚洲成色精品| 亚洲视屏在线播放| 精品999在线观看| 亚洲精品小视频| 国产一区二区三区久久久久久久久| 欧美寡妇偷汉性猛交| 欧美四级电影网站| 久久夜色精品一区| 欧美视频在线一区| 久久综合九色综合欧美就去吻| 欧美区在线播放| 久久亚洲精品视频| 欧美激情亚洲另类| 久久人人97超碰人人澡爱香蕉 | 亚洲精品自在久久| 精品成人国产| 亚洲综合日韩在线| 亚洲精品一区二区在线观看| 欧美一区二区成人6969| 一区二区三区久久精品| 久久亚洲综合| 欧美在线观看视频一区二区| 欧美国产91| 欧美成人一区二区三区在线观看| 国产精品美女www爽爽爽| 亚洲激情亚洲| 在线观看国产日韩| 欧美一级一区| 欧美一区二区三区免费在线看 | 欧美一区二区三区视频| 国产精品99久久久久久白浆小说| 久久在线视频| 免费视频一区| 国内揄拍国内精品久久| 香蕉免费一区二区三区在线观看| 亚洲深夜av| 欧美日韩精品二区第二页| 欧美国产精品一区| 在线免费精品视频| 久久亚洲影音av资源网| 久久综合九色欧美综合狠狠| 国产一区二区三区高清| 欧美一区二区在线看| 久久高清福利视频| 国产日韩在线一区二区三区| 亚洲男人天堂2024| 久久精品国产99精品国产亚洲性色| 国产精品久久久久久久久久直播 | 欧美精品亚洲| 日韩一级欧洲| 亚洲免费一在线| 国产精品v欧美精品∨日韩| 9久re热视频在线精品| 一区二区三区**美女毛片| 欧美日韩精品免费看| 99av国产精品欲麻豆| 亚洲一区二区在线播放| 国产精品日日摸夜夜摸av| 午夜视频一区在线观看| 久久久青草青青国产亚洲免观| 精品成人久久| 欧美黄色免费| 一区二区三区四区国产| 欧美一区午夜精品| 在线观看91久久久久久| 欧美激情精品久久久久久大尺度| 最新国产乱人伦偷精品免费网站| 一区二区三区日韩精品视频| 国产精品乱人伦一区二区 | 亚洲一区免费视频| 久久久人成影片一区二区三区 | 91久久久一线二线三线品牌| 欧美噜噜久久久xxx| 亚洲香蕉在线观看| 久久夜色精品国产欧美乱| 日韩视频在线一区二区三区| 国产精品免费看| 老司机凹凸av亚洲导航| 日韩亚洲在线| 美女国产一区| 亚洲欧美精品| 91久久精品视频| 国产精品亚洲综合天堂夜夜| 老牛嫩草一区二区三区日本| 国产精品99久久久久久白浆小说| 久久精品人人做人人爽电影蜜月| 91久久精品一区二区三区| 国产精品综合久久久| 欧美国产成人精品| 欧美一区日本一区韩国一区| 亚洲精品免费在线观看| 久久久蜜桃一区二区人| 亚洲小视频在线观看| 一区二区三区亚洲| 国产精品私房写真福利视频| 欧美国产精品va在线观看| 欧美一区二区三区男人的天堂 | 亚洲国产激情| 久久综合给合久久狠狠狠97色69| 亚洲伊人久久综合| 亚洲精品久久在线| 红杏aⅴ成人免费视频| 国产精品免费一区二区三区观看| 美女国产一区| 久久久久五月天| 亚洲欧美日韩国产一区二区三区 | 一本色道久久综合亚洲精品不卡| 牛人盗摄一区二区三区视频| 欧美一级视频一区二区| 中文国产一区| 一区二区免费在线观看| 亚洲精品久久在线| 最新日韩在线| 亚洲国产日韩欧美| 亚洲高清自拍| 1024成人网色www| 国内精品视频在线播放| 国产精品人人爽人人做我的可爱| 欧美日韩在线播放三区| 欧美—级在线免费片| 欧美黄色精品| 欧美日韩亚洲综合| 欧美日韩高清在线播放| 欧美黄污视频| 99视频精品全国免费| 亚洲激情一区| 亚洲精品国精品久久99热| 亚洲欧洲综合另类| 亚洲精品美女91| 国产精品99久久久久久久久久久久| 亚洲精品欧美极品| 亚洲私人黄色宅男| 午夜精品一区二区三区电影天堂| 午夜久久美女| 久久精品首页| 免费一级欧美片在线播放| 欧美国产日产韩国视频| 亚洲国产日韩欧美在线99 | 午夜免费日韩视频| 久久精品色图| 欧美福利一区| 日韩一级黄色av| 西西人体一区二区| 久久青草久久| 欧美日韩福利视频| 国产精品久久久久av免费| 国产欧美精品日韩精品| 悠悠资源网亚洲青| 99视频有精品| 久久av在线看| 亚洲国产精品视频一区| 在线一区免费观看| 久久精品二区亚洲w码| 欧美国产综合视频| 国产精品一香蕉国产线看观看| 激情自拍一区| 亚洲图片欧美日产| 久久亚洲春色中文字幕| 亚洲欧洲在线免费| 性色av香蕉一区二区| 欧美国产91| 国产一区二区三区自拍| 日韩视频国产视频| 久久精品人人做人人爽| 亚洲精品在线二区| 久久精品国产99精品国产亚洲性色| 欧美激情一区| 国内精品亚洲| 亚洲尤物影院| 欧美激情中文不卡| 午夜精品久久久久99热蜜桃导演| 免费亚洲电影在线观看| 国产色综合天天综合网| 一区二区三区视频在线播放| 久久久精品国产99久久精品芒果| 亚洲精品欧美日韩专区| 久久久久久夜| 国产日本欧美一区二区三区| 亚洲精品资源| 美日韩精品视频免费看| 亚洲欧美中文另类| 国产精品草草| aa亚洲婷婷| 亚洲国产一区二区三区a毛片|