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

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>
            欧美日韩精品高清| 久久久久网址| 国产精品欧美久久| 欧美一区二区视频在线| 久久se精品一区二区| 亚洲大片av| 欧美激情视频网站| 欧美日韩视频专区在线播放| 亚洲在线第一页| 久久精品国产亚洲aⅴ| 亚洲高清电影| 亚洲裸体视频| 国产午夜精品一区二区三区视频| 久久免费视频网站| 欧美精品成人在线| 性久久久久久久久| 欧美国产视频在线| 香蕉成人久久| 免费成人av在线看| 亚洲欧美在线观看| 欧美成人精品1314www| 亚洲欧美日韩国产一区二区三区| 久久精品国产欧美激情| 野花国产精品入口| 欧美一区二区三区播放老司机 | 一区二区三区日韩欧美| 国产深夜精品| 亚洲精品欧美激情| 伊人春色精品| 中文在线一区| 亚洲精品日韩在线| 久久精品国产综合| 欧美一区二区观看视频| 欧美日韩裸体免费视频| 美国成人毛片| 国产欧美91| 一区二区电影免费观看| 亚洲人成毛片在线播放| 久久精品一区四区| 欧美专区亚洲专区| 欧美午夜宅男影院在线观看| 亚洲第一久久影院| 国产欧美婷婷中文| 在线视频精品一区| 中文精品视频一区二区在线观看| 免费中文字幕日韩欧美| 老司机精品视频一区二区三区| 国产精品日韩久久久| 亚洲精品一品区二品区三品区| 在线观看亚洲视频啊啊啊啊| 亚洲深夜福利在线| 一个色综合av| 欧美日韩国产二区| 亚洲伦理在线观看| 亚洲午夜高清视频| 欧美日本不卡高清| 亚洲免费高清| 一区二区三区四区五区在线 | 91久久精品美女高潮| 亚洲国产一区二区三区在线播 | 国产精品久久久爽爽爽麻豆色哟哟| 亚洲欧洲免费视频| 亚洲精品久久久久久久久久久 | 久久福利影视| 久久久午夜精品| 激情综合网址| 久久综合免费视频影院| 蜜臀av一级做a爰片久久| 亚洲电影免费在线| 免费成人av| 日韩亚洲精品视频| 性色av一区二区怡红| 国产亚洲一区在线| 久久久久久久久伊人| 欧美大片免费观看| 日韩视频免费在线| 国产精品另类一区| 午夜视频一区| 欧美激情成人在线| 亚洲永久精品国产| 国产人成一区二区三区影院| 久久久中精品2020中文| 亚洲欧洲中文日韩久久av乱码| 中文日韩在线视频| 国产亚洲成人一区| 老牛嫩草一区二区三区日本| 亚洲人成在线观看| 午夜精品久久久| 亚洲国产成人在线| 欧美性猛交xxxx乱大交蜜桃| 欧美在线看片| 99精品久久| 暖暖成人免费视频| 亚洲色诱最新| 亚洲成色999久久网站| 欧美日韩免费精品| 久久精品国产精品| 一区二区三区欧美日韩| 麻豆国产精品一区二区三区 | 亚洲午夜视频在线观看| 韩国av一区二区三区四区| 欧美激情欧美激情在线五月| 先锋影音一区二区三区| 91久久久久久久久久久久久| 欧美一区二区三区在线看| 亚洲另类视频| 国内精品视频在线播放| 欧美日韩精品一区二区天天拍小说| 欧美一区二区网站| 亚洲天堂激情| 亚洲破处大片| 欧美激情aaaa| 美脚丝袜一区二区三区在线观看 | 亚洲日本电影| 欧美成人免费在线观看| 午夜精品视频| 日韩午夜免费| 亚洲第一福利在线观看| 国产日韩欧美日韩| 国产精品久久午夜| 欧美日韩精品免费看| 免费不卡在线视频| 久久久欧美精品| 久久精品亚洲乱码伦伦中文 | 浪潮色综合久久天堂| 欧美一区二区三区免费观看| 亚洲影院色无极综合| av不卡在线看| 一本色道久久综合狠狠躁篇的优点| 在线观看不卡av| 伊人婷婷久久| 亚洲大黄网站| 亚洲韩国一区二区三区| ●精品国产综合乱码久久久久| 国产主播一区二区| 国产一区久久久| 国产一区二区三区在线免费观看| 国产女主播视频一区二区| 国产精品乱码人人做人人爱| 欧美日韩亚洲一区二区三区在线观看| 欧美 日韩 国产一区二区在线视频 | 亚洲免费在线电影| 99riav久久精品riav| 日韩午夜精品| 亚洲国产高潮在线观看| 亚洲国产精品ⅴa在线观看| 免费欧美高清视频| 欧美激情精品久久久久久黑人| 欧美jizzhd精品欧美巨大免费| 欧美 日韩 国产一区二区在线视频| 久久久久久久成人| 蜜桃久久av一区| 亚洲国产精品视频| 99热在线精品观看| 亚洲欧美日产图| 久久九九有精品国产23| 久久综合久久美利坚合众国| 欧美二区乱c少妇| 欧美日韩精品一本二本三本| 国产精品va在线播放| 国产亚洲精品成人av久久ww| 韩国av一区二区三区| 亚洲精品中文字幕女同| 亚洲一区二区免费在线| 久久国产精品亚洲va麻豆| 久热这里只精品99re8久| 亚洲激情校园春色| 亚洲一区影院| 免费成人在线观看视频| 国产精品蜜臀在线观看| 亚洲电影免费观看高清完整版| 亚洲麻豆视频| 久久国产精品99久久久久久老狼| 农夫在线精品视频免费观看| 在线视频中文亚洲| 久久最新视频| 国产精品日韩欧美一区| 91久久精品视频| 性欧美8khd高清极品| 欧美激情精品久久久六区热门 | 欧美激情成人在线| 国产日韩一区二区三区在线| 亚洲激情在线| 欧美在线日韩在线| 亚洲美女性视频| 久久综合九色综合欧美狠狠| 国产精品欧美风情| 亚洲蜜桃精久久久久久久| 久久久久久香蕉网| 一区二区免费看| 麻豆精品视频| 国产在线高清精品| 亚洲线精品一区二区三区八戒| 美女日韩在线中文字幕| 亚洲影院污污.| 欧美三区在线视频| 99精品热视频只有精品10| 鲁大师影院一区二区三区| 亚洲欧美日韩另类| 国产精品乱码人人做人人爱|