/******************************************************************************
Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.
*******************************************************************************/
#include<iostream> // 引入标准输入输出库
#include<string.h> // 引入字符串操作库
using namespace std;
const int MAXN = 250; // 我们处理的数字的最大位数
int n, t, i, j, k, la, lb, x[10], a[MAXN], b[MAXN]; // 声明变量
// 函数处理进位
void f(int *a){
for(int i = 0; i < MAXN; i++){ // 遍历数组 a 的每一位
if(a[i] >= 10){ // 如果当前位的值大于等于 10
a[i+1] += a[i] / 10; // 向高一位进位
a[i] %= 10; // 当前位保留个位数
}
}
}
int main(){
cin >> n; // 输入数字 n
x[1] = 1; // 初始化 x[1] 为 1
// 计算 x[i] = i^i 并存储在数组 x 中
for(i = 2; i <= 9; i++){
t = 1; // 初始化 t 为 1
for(j = 1; j <= i; j++){
t *= i; // 计算 i 的 i 次方
}
x[i] = t; // 将 i^i 存储在 x[i] 中
}
// 计算 x[i] 的累积和
for(i = 2; i <= 9; i++)
x[i] += x[i-1];
// 如果 n 是一位数
if(!(n / 10)) // 如果 n 小于 10
cout << x[n]; // 输出单数字 n 的预计算和
else {
// 处理 n 是两位数或更大的情况
for(k = i; k <= n; k++){
memset(a, 0, sizeof(a)); // 重置数组 a
t = k; la = 0;
// 将 k 转换为数字表示并存储在数组 a 中
while(t){
a[la++] = t % 10; // 将 k 的每一位数字存储到数组 a 中
t /= 10; // 去掉 k 的最后一位
}
// 计算 k 的 k 次方并存储在数组 a 中
for(i = 2; i <= k; i++){
for(j = 0; j < la; j++)
a[j] *= k; // 每位数字乘以 k
f(a); // 处理进位
t = MAXN;
while(!a[t]) // 找到数组 a 中的有效位数
t--;
la = t + 1;
}
// 将结果加到数组 b 中
for(i = 0; i < la; i++)
b[i] += a[i]; // 累加数组 a 中的每一位到数组 b 中
f(b); // 处理进位
lb = max(lb, la); // 更新数组 b 的有效位数
if(b[lb]) // 如果最高位有进位
lb++;
}
// 将预计算和 x[9] 加到 b 中
t = x[9]; i = 0;
while(t){
b[i] += t % 10; // 将 x[9] 的每一位加到数组 b 中
t /= 10; // 去掉 x[9] 的最后一位
i++;
}
f(b); // 处理进位
// 按逆序输出数组 b 中的结果
for(i = lb-1; i >= 0; i--)
cout << b[i];
}
return 0;
}
