一看到题，刚开始会感觉很难想，但是可以先从10以内的数开始找规律
比如我们先看到7,设pre(n)表示把n里面的数字累加起来直到n<10
pre(7^7)=pre(823543)=pre(25)=7
因为太大，我们会想，能不能结合快速幂的思想呢
7^7=7^3 * 7^3 * 7
然后这时，我们会发现
pre(7^7)=pre(pre(7^3)*pre(7^3)*7)
再找一个11试试,又发现
pre(11^11)=pre(pre(11^5)*pre(11^5)*11)
pre(11^5)=pre(pre(11^2)*pre(11^2)*11)
再次试我们又能找打一个逆天规律
如果有n=a+b
那么pre(s^n)=pre(pre(s^a)*pre(s^b))
所以这题就可以用类似快速幂的方法解决了
#include<cstdio>
#include<map>
#include<set>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cctype>
#include<vector>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 10000 + 5;
const int INF = 0x3f3f3f3f;int F[MX];int pre(int w) {int ret = 0;while(w) {ret += w % 10;w /= 10;}if(ret > 9) return pre(ret);return ret;
}int solve(int a, int b) {if(b == 1) return pre(a);int ret = solve(a, b / 2);ret *= ret;if(b & 1) ret *= a;return pre(ret);
}int main() {int n;for(int i = 1; i < MX; i++) {F[i] = solve(i, i);}while(~scanf("%d", &n), n) {printf("%d\n", F[n]);}return 0;
}