Project Euler 16
Project Euler,一体何のマラソンなんだかよく分からなくなってきました.
16番は2の1000乗の各桁を足すというもの.
Cとかだと組み込み型ではオーバーフローするから工夫が必要だよね,とかそういうことなのかなぁ?
微妙に出題の意図が分からない.
きっともっとHackな方法があるに違いない!とは思うけど,まだマラソンは始まったばかりなのでこの辺で体力を使うのはやめよう.
typedef unsigned long long uint64; typedef uint64 natural ; natural f16() { const int shoulder = 1000; const int length = 1000; int num[length]; int available = 0; natural sum = 0; for(int i=1; i<length; ++i) { num[i] = 0; } num[0] = 1; for(int i=1; i<=shoulder; ++i) { for(int j=available; j>=0; --j) { num[j] *=2; if( num[j] / 10 ){ num[j+1] += num[j] / 10; num[j] = num[j] % 10; } } if(num[available+1]) { ++available; } } for(int i=0; i<=available; ++i) { sum+=num[i]; } return sum; }
10進数桁ごとの配列にして大きな数を計算する.
前の日記で,typedefの部分をコピペしなかったので今回はコピペ.
この辺,BigDecimalのあるJavaやScript言語で書いたら一瞬なんだろうなぁ.
と思ったのであえてC++です.