약수들의 합 (feat. 백준, 9506번)

약수들의 합
https://www.acmicpc.net/problem/9506

9506번: 약수들의 합

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <set>
#include <numeric>
using namespace std;
inline int gcd(register int a, register int b) {
	return a % b ? gcd(b, a % b) : b;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	while (1) {
		cin >> N;
		if (N == -1)
			break;
		set<int> ans;
		for (register int i = 1; i < N; ++i)
			ans.insert(gcd(i, N));
		if (accumulate(ans.begin(), ans.end(), 0) == N) {
			cout << N;
			for (auto iter = ans.begin(); iter != ans.end(); ++iter)
				if (iter == ans.begin())
					cout << " = " << *iter;
				else
					cout << " + " << *iter;
			cout << "\n";
		}
		else
			cout << N << " is NOT perfect.\n";
	}
	return 0;
}
// *&)*@*

 

 

1. 문제로 주어진 값에 대한 모든 약수는 자료구조 set에 담았습니다. set은 중복된 키는 하나만 남기고 정렬도 가능한 자료구조입니다.
2. 이후 자료구조 set의 모든 키값의 합이 문제로 주어진 값과 같은 경우는 true, 아닌 경우는 false에 해당되는 출력을 해주면 됩니다.