fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. bool flag;
  8. void solve(vector <int> arr, int n, int sum, int cnt)
  9. {
  10. 	if (n == sum)	//덧셈 결과 n과 같다면 이상한 숫자 확인
  11. 	{
  12. 		flag = true;
  13. 		return;
  14. 	}
  15.  
  16. 	for (int i = cnt; i >= 0; i--)
  17. 	{
  18. 		if (flag) return;
  19. 		if (sum + arr[i] > n) continue;
  20. 		solve(arr, n, sum + arr[i], i - 1);
  21. 	}
  22. }
  23. int main(void)
  24. {
  25. 	ios_base::sync_with_stdio(false);
  26. 	cin.tie(NULL);
  27.  
  28. 	int c;
  29. 	cin >> c;
  30.  
  31. 	while (c--)
  32. 	{
  33. 		int n, sum = 1;
  34. 		vector <int> arr;
  35. 		cin >> n;
  36. 		arr.push_back(1);
  37. 		flag = false;
  38. 		for (int i = 2; i * i <= n; i++)		//n의 약수 저장
  39. 		{
  40. 			if (n % i == 0) {
  41. 				arr.push_back(i);
  42. 				arr.push_back(n / i);
  43. 				sum += i + n / i;
  44. 			}
  45. 		}
  46. 		if (sum <= n) {		//약수의 합이 n보다 작거나 같다면 n은 이상한 숫자가 아니다.
  47. 			cout << "not weird" << '\n';
  48. 			continue;
  49. 		}
  50. 		sort(arr.begin(), arr.end());		//약수 저장한 벡터 정렬
  51. 		solve(arr, n, 0, arr.size() - 1);	//백트래킹으로 덧셈 진행
  52.  
  53. 		if (flag) cout << "not ";
  54. 		cout << "weird" << '\n';
  55. 	}
  56. }
Success #stdin #stdout 0s 5568KB
comments (?)
stdin
copy 
2
12
70
stdout
copy 
not weird
weird
https://ideone.com/f3qE3K
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!