AcWing 上会爆栈, 超时, 腾讯云上实测2s出结果。
/*
欧拉计划第56题
大整数乘法, a^b (a, b < 100), 各位数字之和的最大值
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//大整数倒序存储, 输出时需要注意
vector<int> mul(vector<int> A, int k)
{
vector<int> ans;
int n = A.size(), i = 0, c = 0;
while (i < n)
{
c += A[i] * k;
ans.push_back(c % 10);
c /= 10;
i ++;
}
while (c)
{
ans.push_back(c % 10);
c /= 10;
}
return ans;
}
vector<int> init(int a)
{
// int to vector<int>, where a > 1
vector<int> A;
while (a)
{
A.push_back(a % 10);
a /= 10;
}
return A;
}
int f(int a, int b)
{
vector<int> A;
// a^b 的各位数字之和
A = init(1);
for (int i = 1; i <= b; ++ i) A = mul(A, a);
int sum = 0;
for (int i = 0; i < A.size(); ++ i) sum += A[i];
return sum;
}
void print(vector<int> A)
{
for (int i = A.size() - 1; i >= 0; -- i) cout << A[i];
cout << endl;
}
int main(void)
{
int ans = 0, sum;
for (int a = 1; a < 100; ++ a)
for (int b = 1; b < 100; ++ b)
{
sum = f(a, b);
ans = max(ans, sum);
}
cout << ans << endl;
return 0;
}