Google Code Jam 2008 Round1A "Numbers" (問題演習)

問題は「(3+√5)^nの100の位〜1の位を答えよ」、というものです。

この問題の解答例・解説は「プログラミングコンテストチャレンジブック」に載っていますが、私の解答はそれと若干違うものです。

私の解答は次のとおりです。

#include<stdio.h>

unsigned int getbits(unsigned int n){
  int i;
  for(i=0;n>0;i++) n>>=1;
  return i;
}

int main(void){
  unsigned int n,i,j,k,bits;
  unsigned int a_bef=1,b_bef=0,a_next,b_next;

  scanf("%u",&n);
  bits=getbits(n);
  for(i=0;i<bits;i++){
    a_next=(a_bef*a_bef%1000+5*b_bef*b_bef%1000)%1000;
    b_next=2*a_bef*b_bef%1000;
    if(((n>>(bits-i-1))&1)==1){
      a_bef=a_next;
      b_bef=b_next;
      a_next=(3*a_bef+5*b_bef)%1000;
      b_next=(a_bef+3*b_bef)%1000;
    }
    a_bef=a_next;
    b_bef=b_next;
    n-=(1<<bits-i);
  }
  printf("%03u\n",(2*a_bef-1)%1000);
  return 0;

}