#117: 原版(類似題)對應的是 Zerojudge 的 c903


rollfatcat (胖胖貓)

School : No School
ID : 378
IP address : [111.249.80.141]
Last Login :
2023-01-06 19:58:46
d022. 習題 Q-2-13. 無理數的快速冪 (108 高中全國賽, simplifed) -- AP325 | From: [111.249.70.253] | Post Date : 2022-03-20 16:10

觀察 Constraints 可以發現 MaxN=1e9+9,無法只用迴圈 → 快速幂次
s + t√2 = ( x + y√2 ) ^ n,可以將 整數 和 √2 的係數項以「向量」 的形式描述。
快速幂次的矩陣該如何推導呢 ? [ [ x, 2y ], [ y, x ] ]
( x + y√2 ) ^ (n+1) = ( x + y√2 )( x + y√2 )^n = ( x + y√2 ) ( s + t√2 )
s(n+1) = x*s(n) + 2y*t(n)

t (n+1) = y*s(n) +   x*t(n)

init :  ( x + y√2 ) ^ 0 = 1 → s0 = 1, t0 = 0
吳教授的 AP325 有標記是簡化版,原版的內容可以參考 c903: 數字的挑戰
將( 2+√3 )^n 展開後依照 s + t√3 的形式描述,實作細節可以參照這題的做法。

這題的關鍵:找到他的共軛根:( 2 - √3 )^n ,展開後可以得到 s - t√3 的形式。
兩者相加後必定是整數:( 2 + √3 )^n + ( 2 - √3 )^n = 2s,而且 0 < ( 2 - √3 )^n < 1,回到要求可以推得:( 2 + √3 )^n 的整數部分 = 2s - ( 2 - √3 )^n  > 2s - 1。
至於快冪次的矩陣可以從遞迴推導:
( 2+√3 )^( n+1 ) = ( 2+√3 )( 2+√3 )^n = ( 2+√3 ) ( s+t√3 )
s(n+1) = 2s(n) + 3t(n)

t (n+1) =   s(n) + 2t(n)

s0=1 ,t0=0
對於上述的概要如果有不清楚可以參考範例,連結裡面是用  3+√5

 
#118: Re:原版(類似題)對應的是 Zerojudge 的 c903


810848 (路過)

School : 一中
ID : 96
IP address : [125.227.83.73]
Last Login :
2023-02-01 12:06:50
d022. 習題 Q-2-13. 無理數的快速冪 (108 高中全國賽, simplifed) -- AP325 | From: [220.132.230.73] | Post Date : 2022-03-27 21:08

觀察 Constraints 可以發現 MaxN=1e9+9,無法只用迴圈 → 快速幂次
s + t√2 = ( x + y√2 ) ^ n,可以將 整數 和 √2 的係數項以「向量」 的形式描述。
快速幂次的矩陣該如何推導呢 ? [ [ x, 2y ], [ y, x ] ]
( x + y√2 ) ^ (n+1) = ( x + y√2 )( x + y√2 )^n = ( x + y√2 ) ( s + t√2 )
s(n+1) = x*s(n) + 2y*t(n)

t (n+1) = y*s(n) +   x*t(n)

init :  ( x + y√2 ) ^ 0 = 1 → s0 = 1, t0 = 0
吳教授的 AP325 有標記是簡化版,原版的內容可以參考 c903: 數字的挑戰
將( 2+√3 )^n 展開後依照 s + t√3 的形式描述,實作細節可以參照這題的做法。

這題的關鍵:找到他的共軛根:( 2 - √3 )^n ,展開後可以得到 s - t√3 的形式。
兩者相加後必定是整數:( 2 + √3 )^n + ( 2 - √3 )^n = 2s,而且 0 < ( 2 - √3 )^n < 1,回到要求可以推得:( 2 + √3 )^n 的整數部分 = 2s - ( 2 - √3 )^n  > 2s - 1。
至於快冪次的矩陣可以從遞迴推導:
( 2+√3 )^( n+1 ) = ( 2+√3 )( 2+√3 )^n = ( 2+√3 ) ( s+t√3 )
s(n+1) = 2s(n) + 3t(n)

t (n+1) =   s(n) + 2t(n)

s0=1 ,t0=0
對於上述的概要如果有不清楚可以參考範例,連結裡面是用  3+√5


原版的題目是其實是全國賽的題目,題目是算出第N組C(m,2) = n^2的解mod 1e9+7。

 
ZeroJudge Forum