记录编号	110465	评测结果	AAAAAAAAAAAAEA
题目名称	[暑假培训2012] 残酷的数学老师	最终得分	92
用户昵称	JSX	是否通过	未通过
代码语言	C++	运行时间	1.471 s
提交时间	2014-07-11 17:02:24	内存使用	0.42 MiB

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