FOJ Problem 1068 An Interesting Set

一，问题描述

 题目翻译：

二，问题分析

对于集合S，满足两个条件（二者满足一个就行）

1.条件1，显然1-9是满足的，而其他数字的判断可以利用取余来实现

2.条件2，可以利用set集合的性质来判断，结合条件1，所有偶数都是满足集合S的

3.根据题意，正整数K是小于500的，我们采用打表法，把集合S的前500个元素都记录下来

三，问题解答

#include<iostream>
#include<set>
#include<cstdio>
using namespace std;

int num[505];					//用于存储满足S集合条件的数
set<int> s;
set<int>::iterator it;
bool isin(int a) {
	int total = 0;				//用于求和
	int muti = 1;				//用于求乘积
	int num;
	//条件一，需要判断是否偶数，偶数肯定属于集合S（2是属于集合S的）
	if (a % 2 == 0) {
		it = s.find(a / 2);			//判断a/2是否处于集合中
		if (it != s.end()) {			//处于集合S中
			return true;
		}
	}
	//条件二
	while (a) {		
		num = a % 10;
		if (num == 0) {
			return false;
		}
		total += num;
		muti *= num;
		a /= 10;
	}
	if (total != muti) {				//各数字和与乘积不等，不满足条件
		return false;
	}
	return true;
}
//打表初始化
void init() {
	int i, j;
	for (i = 1, j = 1; j <= 500; i++) {		//i一直增加，直到num数组存储满，即打表完成时
		if (isin(i)) {			
			num[j++] = i;
			s.insert(set<int>::value_type(i));
		}
	}
}
int main() {
	int N, k;
	cin >> N;
	init();
	while (N--) {
		cin >> k;
		cout << num[k] << endl;
	}

	return 0;
}