记录编号	92974	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]麦森数	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2014-03-23 17:35:48	内存使用	0.31 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
struct bign
{
   int num[800];
   int end;
};//用于存高精度的结构
const double logtwo =0.30102999566398;//log2常数，加快速度
bign quickpow(int exp);//快速幂
int getpos(int exp);//算位数的
void print(bign k);//输出
bign times(bign plusa,bign plusb);//高精度乘法
int main()
{
  freopen("mason.in","r",stdin);
  freopen("mason.out","w",stdout);
  int n;
  scanf("%d",&n);
  printf("%d\n",int(n*logtwo)+1);
  print(quickpow(n));
  //system("pause");
  return 0;
}
//======================================================================
void print(bign k)
{ 
   k.num[1]--;
   int md=0;
   for(int a=500;a>=1;a--)
   {
     md++;
     printf("%d",k.num[a]);
     if (md%50==0)
       cout<<endl;
   }
   return ;
}
//我觉得这个程序没什么解释的啊
//=====================================================================
bign times(bign plusa,bign plusb)
{
   bign product;
   memset(product.num,0,sizeof(product.num));
   for(int b=1;b<=plusb.end;b++)
     for(int a=1;a<=plusa.end;a++)
       if (a+b-1>500)//超过500位的不要存
         break;
       else
        product.num[a+b-1]+=plusa.num[a]*plusb.num[b];
   product.end=1;
//进位
   while (product.end<=plusa.end*plusb.end+20&&product.end<=500)
   {
     product.num[product.end+1]+=product.num[product.end]/10;
     product.num[product.end]=product.num[product.end]%10;
     product.end++;
   }
   product.end--;
   return product;
}
//======================================================================
int getpos(int exp)
{
    return int(exp*logtwo)+1;
}
//=======================================================================
bign quickpow(int exp)
{
   bign k;
   memset(k.num,0,sizeof(k.num));
      if (exp==1)
      {
        k.end=1;
        k.num[1]=2;return k;
      }
      k=quickpow(exp/2);
      k=times(k,k);
      bign two=quickpow(1);
      if (exp%2==1)
        k=times(k,two);
   return k;
}