`
- 홀수는 n +(n+1)로 표현가능
- 짝수의 경우 다음과 같이 생각할 수 있다.
- $6 = 2+2+2$ 에서 앞 뒤로 1을 빼고 더하면 $1+2+3$
- $14 = 2*7 = (-1+0+1)+2+3+4+5 = 2+3+4+5$
그렇다면 12인 경우 답은 3+4+5인데 2+2+2+2+2+2에서 위와 같이 하긴 힘들다.
그래서 좀 더 생각해보니 $12 = 2^2*3$ 이고 4로 나누었을 때 풀이가 나오는 것이 가능하다.
이렇게 규칙을 찾았을 때, 짝수여도 2를 제외한 소수가 있을 경우 연속된 수로 표현이 가능하다.
결국 가능하지 않은 경우는 2의 제곱수에 해당하는 것들이라 할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class B16464 {
static int T,N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
for(int t=0;t<T;t++) {
N = Integer.parseInt(br.readLine());
while(N!=1) {
if(N%2==1) {
sb.append("Gazua").append("\n");
break;
}
N/=2;
}
if(N==1)
sb.append("GoHanGang").append("\n");
}
System.out.println(sb);
}
}
|