問題はこちら
No.344 ある無理数の累乗 - yukicoder
Dashboard - Round 1A 2008 - Google Code Jamの類題
この問題は、自分がまだプログラミングを知らなかった頃に見つけて、自力で数学的な答えにたどり着いた思い出深い問題。
α=1+√3、β=1-√3とし、a[n]:=α^n+β^nを考える。これは文字α,βに関する対称式なので、α+βとαβで表せ、α+β=2、αβ=-2よりa[n]は整数。
(文字式として計算すれば)a[n]=(α+β)a[n-1]-αβa[n-2]が得られるので、a[n]=2(a[n-1]+a[n-2])となる。
求めるべきはα^nだったが、-1<β<0なのでfloor(α^n)はnが偶数の時a[n]-1、奇数の時a[n]となる。
a[n]は整数なので、a[n] mod 1000は高々(1000^2)項からなる循環節をもつ。
ということでこの循環節を求めると、a[604]以降はa[4]と一致。
(プログラムで確かめるのが面倒だったので、エクセルで目視確認した)
ということで、次のように実装できる
int main(){ int a[620],i,n; a[0]=a[1]=2; for(i=2;i<610;i++)a[i]=(a[i-1]+a[i-2])*2%1000; scanf("%d",&n); if(n%2==0)i=-1; else i=0; if(n<4)printf("%d",a[n]+i); else if(n%600<4)printf("%d",a[n%600+600]+i); else printf("%d",a[n%600]+i); //単にn%600だと、n>4かつn%600<4のときに困る(この時の値はa[0]~a[3]ではない) return 0; }
ここで他人のコードを眺めていると「a[(n-4)%600+4]+…」という記述を目にした
どうやらこれで場合分けをしなくて済むらしい
n-4が非負なら全体は4~603の値を返し、負なら、即ちn<4なら(n-4)%600はn-4になるので全体はnになる…なるほど。
ということでこれを使って縮めると
a[610]={2,2},n; main(i){ for(scanf("%d",&n);i++<605;a[i]=(a[i-1]+a[i-2])*2%1000); n=!printf("%d",a[(n-4)%600+4]+~n%2); //~n%2でnが偶数のとき-1、奇数の時0になる }
116B
α^n+β^nを考えるのは天下り的かなとは思うものの、例えば黄金比の冪乗が整数に近づいていくことの証明(c.f.ほとんど整数 - Wikipedia)としてそれなりに有名なのかも