问题 D: 【高精度】高精度幂

时间限制: 1 Sec  内存限制: 64 MB

题目描述

经过测试，修罗王发现打开魔法手铐的方法是需要求一个正整数a(1<a<10100)的N（1<N<108）次方，但只要求输出最后1000位（若不够1000位，则只输出实际位数，若超过1000位，即使首位为0也同样输出）。

 

输入

包含两个数字，即a和N。

 

输出

输出结果的最后1000位。

 

样例输入

复制样例数据

2 10

样例输出

1024

注意c数组不能只取1000为万一第1000为为0不就舍掉了，到最后在输出1000位

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;
char ans[2005];
int tot;

void solve(char p[], char a[]){
	int c[2005];
	memset(c, 0, sizeof(c));
	int lenp = strlen(p), lena = strlen(a);
	lenp = min(lenp, 1000), lena = min(lena, 1000);
	for (int i = 0; i < lenp; i++){
		for (int j = 0; j < lena; j++){
			c[i + j] += (p[i] - '0') * (a[j] - '0');
			if(c[i + j] > 9){
				c[i + j + 1] += c[i + j] / 10;
				c[i + j] %= 10;
			}
		}
	}
	int cnt = lena + lenp;
	while(c[cnt] == 0 && cnt > 0) cnt--;
	for (int i = 0; i <= cnt; i++){
		p[i] = c[i] + '0';
	}
	p[cnt + 1] = '\0';
	tot = cnt;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%s %d", ans, &n);
	if(!n){
		printf("1\n");
		return 0;
	}
	int id;
	reverse(ans, ans + strlen(ans));
	char p[2005];
	strcpy(p, "1");
	while(n){
		if(n & 1){
			solve(p, ans);
			id = tot;
		}
		solve(ans, ans);
		n >>= 1;
	}
	if(id >= 1000) id = 999;
	for (int i = id; i >= 0; i--){
		printf("%c", p[i]);
	}
	printf("\n");

	return 0;
}
/**/