比赛 20140711B班小测 评测结果 AAAAAAAAAAAATA
题目名称 残酷的数学老师 最终得分 92
用户昵称 JSX 运行时间 2.397 s
代码语言 C++ 内存使用 0.33 MiB
提交时间 2014-07-11 16:27:24
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<string>
  4. #include<cmath>
  5. #include<cstdlib>
  6. using namespace std;
  7. const unsigned int MAX = 10000;
  8. const long long WIDTHMAX = 10;
  9. const unsigned int WIDTH = 1;
  10. typedef struct node
  11. {
  12. long long val[MAX];
  13. unsigned int size;
  14. } BigInt;
  15.  
  16. string s1;
  17. bool bj=0;
  18. BigInt StrToBigInt(string s);
  19. void PrintBigInt(const BigInt & a,int flag);
  20. BigInt MulBigInt(const BigInt & a, const BigInt & b);
  21. void PowBigInt(BigInt & c, const BigInt & a, unsigned int n);
  22. void PowBigInt_2(BigInt & c, const BigInt & a, unsigned int n,int& flag);
  23.  
  24. int main()
  25. {
  26. freopen("cruel1.in","r",stdin);
  27. freopen("cruel1.out","w",stdout);
  28. string s,s1;
  29. cin>>s;
  30. int n,flag=0;
  31. cin>>n;
  32. for(int i=0;i<s.size();++i)
  33. {
  34. if(s[i]=='.')
  35. {
  36. int m=s.size();
  37. s.erase(i,1);
  38. flag=s.size()-i;
  39. bj=1;
  40. break;
  41. }
  42. }
  43. flag*=n;
  44. BigInt a,c;
  45. a = StrToBigInt(s);
  46. PowBigInt_2(c, a, n,flag);
  47. PrintBigInt(c,flag);
  48. return 0;
  49. }
  50.  
  51. void PrintBigInt(const BigInt & a,int flag)
  52. {
  53. for(int i=a.size-1;i>=0;--i)
  54. {
  55. if((a.size-i)%70==0)
  56. {
  57. printf("%d\n",a.val[i]);
  58. }
  59. else
  60. {
  61. printf("%d",a.val[i]);
  62. }
  63. }
  64. }
  65.  
  66. void PowBigInt_2(BigInt & c, const BigInt & a, unsigned int n,int& flag)
  67. {
  68. int stack[MAX] = {0};
  69. int top = 0;
  70. while (n > 0)
  71. {
  72. stack[top++] = n % 2;
  73. n /= 2;
  74. }
  75. c.size = c.val[0] = 1;
  76. for (int i=top-1; i>=0; i--)
  77. {
  78. c = MulBigInt(c, c);
  79. if (stack[i] == 1)
  80. c = MulBigInt(a, c);
  81. }
  82. }
  83.  
  84. BigInt StrToBigInt(string s)
  85. {
  86. BigInt a;
  87. a.size = 0;
  88. int i = s.size();
  89. unsigned long long sum = 0;
  90. while ( i>=WIDTH)
  91. {
  92. for (int j=i-WIDTH; j<i; j++)
  93. sum = sum * 10 + (s[j] - '0');
  94. a.val[a.size++] = sum;
  95. sum = 0;
  96. i -= WIDTH;
  97. }
  98. if (i > 0)
  99. {
  100. for (int j=0; j<i; j++)
  101. sum = sum * 10 + (s[j] - '0');
  102. a.val[a.size++] = sum;
  103. }
  104. return a;
  105. }
  106.  
  107. BigInt MulBigInt(const BigInt & a, const BigInt & b)
  108. {
  109. if (a.size == 1 && a.val[0] == 0)
  110. return a;
  111. if (b.size == 1 && b.val[0] == 0)
  112. return b;
  113. BigInt c;
  114. for (int i=0; i<MAX; i++)
  115. c.val[i] = 0;
  116. for (int i=0, j=0; i<b.size; i++)
  117. {
  118. for (j=0; j<a.size; j++)
  119. {
  120. c.val[i+j] += a.val[j] * b.val[i];
  121. c.val[i+j+1] += c.val[i+j] / WIDTHMAX;
  122. c.val[i+j] %= WIDTHMAX;
  123. }
  124. c.size = i + j;
  125. if (c.val[c.size] != 0)//最高位有进位
  126. c.size++;
  127. }
  128. return c;
  129. }
  130.