Google Code Jam 2008 Round1A "Numbers" (Exercise)

Problem is here.

This problem's answer is explained in Japanese book "programming contest challenge book"(プログラミングコンテストチャレンジブック). However, my answer is a little different from that.

My answer is next.

#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;

}