题解：SP25728 NNUM - One of the Simpsons symbols

题意：

求

n

位自幂数的个数。

自幂数指一个

n

位数，它的每个数位上的数字的

n

次幂之和等于它本身。

1 \le n \le 8

。

思路：

正常的爆搜是

O(10 ^ n \times n)

的，不可过。注意到数据范围很小，于是本地打表即可。

代码（含有打表程序）:

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 15;
int n, ans, tmp[N] = {0, 9, 0, 4, 3, 3, 1, 4, 3};

inline void dfs(int x) {
	// cerr << "n:" << n << '\n';

	if(x == n + 1) {
		int k = 0, res = 0;

		for(int i = 1 ; i <= n ; ++ i)
			k += tmp[i] * pow(10, n - i), res += pow(tmp[i], n);
		
		if(res == k) ++ ans;

		return ;
	}

	if(x != 1) {
		tmp[x] = 0;

		dfs(x + 1);
	}

	for(int i = 1 ; i <= 9 ; ++ i)
		tmp[x] = i, dfs(x + 1);
	
	return ;
}

signed main() {
	// ios_base :: sync_with_stdio(NULL);
	// cin.tie(nullptr);
	// cout.tie(nullptr);

	cin >> n;

	cout << tmp[n];

	// for(int i = 1 ; i <= 8 ; ++ i) {
	// 	n = i;
		
	// 	ans = 0;

	// 	dfs(1);
		
	// 	cout << ans << ' ';
	// }

	return 0;
}

题解：SP25728 NNUM - One of the Simpsons symbols

文章操作

题意：

思路：

相关推荐

评论

题解：SP25728 NNUM - One of the Simpsons symbols