프로그램 명: sumsets
제한시간: 2
초
양의 정수 N (1 <= N <= 1,000,000) 이 주어질 때 2 의 멱집합(2^0,2^1,2^2,...)의 합으로 나타낼수 있는 가지수를
구하는게 문제이다.
예로 , N 이 7 인 경우
- 1+1+1+1+1+1+1
- 1+1+1+1+1+2
- 1+1+1+2+2
- 1+1+1+4
- 1+2+2+2
- 1+2+4
6 가지가 존재한다.
입력
N 이 주어진다.
출력
1,2,4,8,16,... 의 합으로 나타낼수 있는 가지수를 마지막 9 자리만 출력한다.
입출력 예
입력
7
출력
6
출처:USACO 2005 January Silver
[질/답]
[제출 현황]
[푼 후(2)]