読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.344 ある無理数の累乗

問題はこちら
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)としてそれなりに有名なのかも