高精快速幂0pts求助
查看原帖
高精快速幂0pts求助
780641
WD2c0mP楼主2023/1/5 16:54

高精快速幂0pts求助

#include <bits/stdc++.h>
using namespace std;
int mson[3100010], a[3100010], ans[3100010], la, l;
void msonchenga() {
	for (int i = 1; i <= l; i ++) {
		int x = 0;
		for (int j = 1; j <= la; j ++) {
			ans[i + j - 1] = mson[i] * a[j] + x + ans[i + j - 1];
			x = ans[i + j - 1] / 10;
			ans[i + j - 1] %= 10;
		}
		ans[i + la] = x;
	}
	int ltn = l + la;
	memcpy(mson, ans, sizeof(mson));
	while (mson[ltn] == 0 && ltn > 1) ltn --;
	l = ltn;
}
void achenga() {
	for (int i = 1; i <= la; i ++) {
		int x = 0;
		for (int j = 1; j <= la; j ++) {
			ans[i + j - 1] = a[i] * a[j] + x + ans[i + j - 1];
			x = ans[i + j - 1] / 10;
			ans[i + j - 1] %= 10;
		}
		ans[i + la] = x;
	}
	int ltn = la + la;
	memcpy(a, ans, sizeof(a));
	while (a[ltn] == 0 && ltn > 1) ltn --;
	la = ltn;
}
int main() {
	int p;
	cin >> p;
	a[1] = 2;
	la = 1;
	mson[1] = l = 1;
	while (p) {
		if (p & 1)
			msonchenga();
		achenga();
		p >>= 1;
	}
	cout << l << endl;
	for (int i = 1; i <= 500; i ++) {
		if (i != 500) cout << mson[500 - i + 1];
		else cout << mson[500 - i + 1] - 1;
		if (i % 50 == 0 && i != 500) cout << endl;
	}

	return 0;
}
2023/1/5 16:54
加载中...