OIBH 2006 模擬試題3 prob 3 情书抄写员

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

http://mail.bashu.cn:8080/BSoiOnline/showproblem?problem_id=1629





顯而易見可以得到第n天的情書數量有F(n) = F(n-1) + k * F(n-2)









先講結論，gcd(F(a), F(b)) = F(gcd(a, b))

以下證明 by willyliu

Lemma 1 : gcd(F(n), k) = 1

proof :

gcd(F(n), k)

= gcd(F(n-1) +F(n-2)k, k)

= gcd(F(n-1), k)

= ... = 1



Lemma 2 : gcd(F(n), F(n+1)) = 1

proof :

gcd(F(n), F(n+1))

= gcd(F(n), F(n) + F(n-1)k)

= gcd(F(n), F(n-1)) ∵Lemma 1

= ... = 1



Lemma 3 : F(a+b) = F(a)F(b+1) + F(a-1)F(b)k

proof :

F(a+b)

= F(a+b-1) + F(a+b-2)k

Induction on b,

= ( F(a)F(b) + F(a-1)F(b-1)k ) + ( F(a)F(b-1) + F(a-1)F(b-2)k )k

= F(a) * ( F(b) + F(b-1)k ) + F(a-1) * ( F(b-1) + F(b-2)k )k

= F(a)F(b+1) + F(a-1)F(b)k



Theorem : gcd(F(a), F(b)) = F(gcd(a, b))

proof :

WLDG a ≧ b,

gcd( F(a), F(b) )

= gcd( F(a-b + b), F(b) )

= gcd( F(a-b)F(b+1) + F(a-b-1)F(b), F(b) ) ∵Lemma 3

= gcd( F(a-b)F(b+1), F(b) )

= gcd( F(a-b), F(b) ) ∵Lemma 2

= gcd( F(a mod b), F(b) )

= F( gcd(a, b) ) Q.E.D.