# [Gold V] 예쁜 숫자 [문제 링크](https://www.acmicpc.net/problem/3152) ## 문제 설명 <p>p는 2보다 큰 정수이다. 다음과 같은 규칙으로 무한 이진 트리의 각 노드에 정수인 숫자가 매겨진다.</p> <ul> <li>루트 노드에는 1을 매긴다.</li> <li>노드에 x가 매겨져 있다면 해당 노드의 왼쪽 자식 노드에는 p * x, 오른쪽 자식 노드에는 p * x + 1이 매겨진다.</li> </ul> <p>예를 들어 p = 3 일때 트리의 시작 부분은 다음과 같을 것이다.</p> <p style="text-align:center"><img src="https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/userupload/insu_nym/20160121/20ac1a532aec950c639dcc70a7a6366e.png" style="height:305px; width:587px"></p> <p>어떤 숫자는 무한 이진 트리 내의 서로 다른 두 노드에 매겨진 두 숫자의 합으로 표현 할 수 있는 방법이 한 가지면 "예쁜 숫자"로 분류된다. 주어진 p로 만든 무한 이진 트리 내에서 n₁, n₂, n₃, n₄가 "예쁜"지 출력하는 프로그램을 작성하라.</p> ## 입력 <p>한 줄에 정수 p, n₁, n₂, n₃, n₄가 차례로 주어진다. (2 < p < 50, 0 < n₁ < 10¹⁸, 0 < n₂ < 10¹⁸, 0 < n₃ < 10¹⁸, 0 < n₄ < 10¹⁸)</p> ## 출력 <p>한 줄에 차례로 n₁, n₂, n₃, n₄가 예쁘면 1을, 아니면 0을 출력한다.</p> ## 풀이 #### p진법으로 n을 만드는 경우를 가정했다. 합을 만드는 방법을 유일하게 하기 위해서는 계수가 1인 항의 수를 제한해야 했다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; ull p, n1, n2, n3, n4; bool solve(ull n) { ull mod = 1; while(mod<=n/p) mod *= p; if(mod == n) return false; // 제곱수인 경우 불가능 int total=0; // 총 항의 수 int cnt=0; // 계수가 1인 항의 수 while(mod>=1) { if(n/mod>2) return false; // 계수가 3 이상인 경우 불가능 if(n/mod==1) cnt++; if(n/mod>=1) total++; n %= mod; mod /= p; } return !(total>=3 && cnt>=2); // 항이 3개 이상이고, 그중 두개 이상의 항의 계수가 1이면 불가능 } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> p >> n1 >> n2 >> n3 >> n4; cout << solve(n1) << ' ' << solve(n2) << ' ' << solve(n3) << ' ' << solve(n4); } ```