[2019 SCPC 1차 예선]
\(1\) 이상의 정수를 받아서 다음의 규칙에 따른 “작업”을 반복하여 결국 \(1\) 을 만드는 게임을 하려고 한다.
아래 규칙은 한번의 작업에 대한 것이고, 작업의 결과로 만들어지는 수에 작업을 수행하는 것을 반복한다. 규칙에도 나와 있듯이 현재 수가 \(1\) 인 경우는 작업을 하지 않고 멈춘다.
1. 만약 수가 \(1\) 이면 작업을 하지 않고 멈춘다.
2. 만약 수가 \(1\) 이 아닌 홀수이면 \(1\) 을 더한다.
3. 만약 수가 짝수이면 \(2\) 로 나눈다.
예를 들어, 받은 수가 \(2\) 인 경우는 \(2\rightarrow1\) 로 \(1\) 회의 작업 후에 멈춘다.
받은 수가 \(4\) 인 경우는 \(4→2→1\) 로 \(2\) 회의 작업 후에 멈춘다.
받은 수가 \(3\) 인 경우는 \(3→4→2→1\) 로 \(3\) 회의 작업 후에 멈춘다.
받은 수가 \(6\) 인 경우는 \(6→3→4→2→1\) 로 \(4\) 회의 작업 후에 멈춘다.
앞의 예 들에서 볼 수 있듯이, 받은 수가 \(3\) 인 경우의 작업 횟수를 알면 받은 수가 \(6\)인 경우의 작업 횟수를 바로 계산할 수 있다는 것을 알 수 있다.
두 정수 \(N_1\)과 \(N_2\)를 입력으로 받아서 (\(1≤N_1≤N_2≤10^6\)), \(N_1,N_1+1,N_1+2,…,N_2\)의 작업 회수를 모두 더한 값을 계산하는 프로그램을 작성하라.
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,
이후 차례로 \(T\) 개의 테스트 케이스가 주어진다. (\(1 ≤ T ≤ 10,000\))
각 테스트 케이스의 첫 줄에는 정수 \(N_1\)과 \(N_2\)가 주어진다. (\(1≤N_1≤N_2≤10^6\))
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 \(C\)는 테스트 케이스의 번호이다.
그 다음 줄에, \(N_1,N_1+1,N_1+2,…,N_2\)의 작업 회수를 모두 더한 값을 출력한다.
| 입력 |
|---|
| 2 3 6 6 6 |
| 출력 |
|---|
| Case #1 14 Case #2 4 |