POJ/2748.cc

   1 #include <cstdio>
   2 #include <algorithm>
   3
   4 using namespace std;
   5
   6 const int maxn=150000;
   7
   8 int f[maxn]={0,1,1,2};
   9
  10 int main()
  11 {
  12         int tcase;
  13         long long n;
  14         scanf("%d",&tcase);
  15         for (int i=3; i<maxn; ++i) f[i]=(f[i-1]+f[i-2])%100000;
  16         while (tcase--)
  17         {
  18                 scanf("%lld",&n);
  19                 --n<<=1;
  20                 printf("%d\n",f[++n%maxn]);
  21         }
  22         return 0;
  23 }