比赛 |
20140711B班小测 |
评测结果 |
AAAAAAAAAAAATA |
题目名称 |
残酷的数学老师 |
最终得分 |
92 |
用户昵称 |
JSX |
运行时间 |
2.397 s |
代码语言 |
C++ |
内存使用 |
0.33 MiB |
提交时间 |
2014-07-11 16:27:24 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<cstdlib>
using namespace std;
const unsigned int MAX = 10000;
const long long WIDTHMAX = 10;
const unsigned int WIDTH = 1;
typedef struct node
{
long long val[MAX];
unsigned int size;
} BigInt;
string s1;
bool bj=0;
BigInt StrToBigInt(string s);
void PrintBigInt(const BigInt & a,int flag);
BigInt MulBigInt(const BigInt & a, const BigInt & b);
void PowBigInt(BigInt & c, const BigInt & a, unsigned int n);
void PowBigInt_2(BigInt & c, const BigInt & a, unsigned int n,int& flag);
int main()
{
freopen("cruel1.in","r",stdin);
freopen("cruel1.out","w",stdout);
string s,s1;
cin>>s;
int n,flag=0;
cin>>n;
for(int i=0;i<s.size();++i)
{
if(s[i]=='.')
{
int m=s.size();
s.erase(i,1);
flag=s.size()-i;
bj=1;
break;
}
}
flag*=n;
BigInt a,c;
a = StrToBigInt(s);
PowBigInt_2(c, a, n,flag);
PrintBigInt(c,flag);
return 0;
}
void PrintBigInt(const BigInt & a,int flag)
{
for(int i=a.size-1;i>=0;--i)
{
if((a.size-i)%70==0)
{
printf("%d\n",a.val[i]);
}
else
{
printf("%d",a.val[i]);
}
}
}
void PowBigInt_2(BigInt & c, const BigInt & a, unsigned int n,int& flag)
{
int stack[MAX] = {0};
int top = 0;
while (n > 0)
{
stack[top++] = n % 2;
n /= 2;
}
c.size = c.val[0] = 1;
for (int i=top-1; i>=0; i--)
{
c = MulBigInt(c, c);
if (stack[i] == 1)
c = MulBigInt(a, c);
}
}
BigInt StrToBigInt(string s)
{
BigInt a;
a.size = 0;
int i = s.size();
unsigned long long sum = 0;
while ( i>=WIDTH)
{
for (int j=i-WIDTH; j<i; j++)
sum = sum * 10 + (s[j] - '0');
a.val[a.size++] = sum;
sum = 0;
i -= WIDTH;
}
if (i > 0)
{
for (int j=0; j<i; j++)
sum = sum * 10 + (s[j] - '0');
a.val[a.size++] = sum;
}
return a;
}
BigInt MulBigInt(const BigInt & a, const BigInt & b)
{
if (a.size == 1 && a.val[0] == 0)
return a;
if (b.size == 1 && b.val[0] == 0)
return b;
BigInt c;
for (int i=0; i<MAX; i++)
c.val[i] = 0;
for (int i=0, j=0; i<b.size; i++)
{
for (j=0; j<a.size; j++)
{
c.val[i+j] += a.val[j] * b.val[i];
c.val[i+j+1] += c.val[i+j] / WIDTHMAX;
c.val[i+j] %= WIDTHMAX;
}
c.size = i + j;
if (c.val[c.size] != 0)//最高位有进位
c.size++;
}
return c;
}