高精度乘除低精度 + 微擾證明

題目鏈接：

https://www.acwing.com/problem/content/116/

思路：

通過微擾證明發現所有大臣要按照 \(a * b\) 的大小來排序，然后就是高精度的一個乘除了。

代碼：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
pair <int, int> p[N];
vector <int> mul(vector <int> a, int b){
	vector <int> c;
	int t = 0;
	for (int i = 0; i < a.size(); i ++ ){
		t += a[i] * b;
		c.push_back(t % 10);
		t /= 10;
	}
	while (t){
		c.push_back(t % 10);
		t /= 10;
	}
	return c;
}
vector <int> div(vector <int> a, int b){
	vector <int> c;
	bool f = true;	//去掉前導0 
	for (int i = a.size() - 1, t = 0; i >= 0; i -- ){
		t = t * 10 + a[i];
		int x = t / b;
		if (!f || x){
			f = false;
			c.push_back(x);
		}
		t %= b;
	}
	reverse(c.begin(), c.end());
	return c;
}
vector <int> max_vec(vector <int> a, vector <int> b){
	if (a.size() > b.size()) return a;
	if (a.size() < b.size()) return b;
	if ( vector <int> (a.rbegin(), a.rend()) > vector <int> (b.rbegin(), b.rend()) ) return a;
	return b;
}
int main(){
	cin >> n;
	for (int i = 0; i <= n; i ++ ){
		int a, b;
		cin >> a >> b;
		p[i] = {a * b, a};
	}
	sort(p + 1, p + n + 1);
	vector <int> s(1, 1), ans(1, 0);
	for (int i = 0 ; i <= n; i ++ ){
		if (i) ans = max_vec( ans, div(s, p[i].first / p[i].second) );
		s = mul(s, p[i].second);
	}
	for (int i = ans.size() - 1; i >= 0; i -- )
		cout << ans[i];
	cout << "\n";
	return 0;
}

高精快速冪

https://www.luogu.com.cn/problem/P1045

輸入 \(p\)，計算 \(2^p - 1\) 的位數和最后 500 位數字（用十進制高精度數表示）。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int ans[1010], a[1010], t[1010];
void solve(){
	memset(t, 0, sizeof t);
	for (int i = 1; i <= 500; i ++ )
		for (int j = 1; j <= 500; j ++ )
			t[i + j - 1] += ans[i] * a[j];
	for (int i = 1; i <= 500; i ++ ){
		t[i + 1] += t[i] / 10;
		t[i] %= 10;
	}
	memcpy(ans, t, sizeof ans);
}
void solvea(){
	memset(t, 0, sizeof t);
	for (int i = 1; i <= 500; i ++ )
		for (int j = 1; j <= 500; j ++ )
			t[i + j - 1] += a[i] * a[j];
	for (int i = 1; i <= 500; i ++ ){
		t[i + 1] += t[i] / 10;
		t[i] %= 10;
	}
	memcpy(a, t, sizeof a);
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int p;
	cin >> p;
	cout << (int)(log10(2) * p + 1) << "\n";
	ans[1] = 1;
	a[1] = 2;
	while(p){
		if (p & 1) solve();
		p >>= 1;
		solvea();
	}
	ans[1] -= 1;
	for (int i = 500; i >= 1; i -- ){
		if (i != 500 && i % 50 == 0) cout << "\n";
		cout << ans[i];
	}
	return 0;
}