Codeforces Round #747 (Div. 2)-B. Special Numbers

문제 설명

지우는 양의 정수로 이루어진 수열을 매우 좋아한다. 따라서 지우의 선생님인 혜린은 지우에게 오직 특별한 숫자로만 이루어진 수열에 관한 문제를 냈다.

서로 다른 음이 아닌 $n$의 제곱수의 합으로 양의 정수를 나타낼 수 있으면 그 수를 특별하다고 한다. 예를 들어 $n = 4$ 일때 $17$은 특별하다. 왜냐하면 $4^0 + 4^2 = 1 + 16 = 17$ 로 표현 할 수 있기 때문이다. 하지만 $9$ 는 그렇지 않다.

지우는 특별한 수가 오름차순으로 정렬되어있는 수열 중에서 $k$번째 수를 구해야한다. 이 숫자는 매우 크기 때문에 값을 $10^9 + 7$ 로 나눈 나머지값을 구한다.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 두 정수 $n$과 $k (2 \le n \le 10^9; 1 \le k \le 10^9)$이 주어진다.

Output
각 테스트케이스마다 오름차순으로 정렬되어 있는 $k$번째 특별한 숫자를 $10^9 + 7$ 으로 나눈 나머지 값을 구한다.

Example
input
3
3 4
2 12
105 564

output
9
12
3595374

문제 접근

사용한 알고리즘: 수학, 비트마스크
걸린 시간 : 00:09
내가 이 문제를 풀었다는 것에 정말 내적 만족했었던 문제였다. 나도 점점 발전을 하는 걸까?

나는 처음 문제를 풀때 딱 문제를 보고 이해가 안되면 그냥 노트에 예시를 적어보곤 한다. 이 문제도 맨 아래에 있는 예시를 보면서 문제의 답이 어떻게 도출되는지 노트에 적으면서 관찰해봤다.

그 예시는 $n = 3$ 일때 특별한 수의 수열이 $[1, 3, 4, 9 ... ]$ 이라는 것이다. $k = 1$ 인 경우 $3^0$, $k=2$ 인 경우 $3^1$ , $k=3$ 인 경우 $3^1 + 3^0$, $k=4$ 인 경우 $3^2$ 이런 식으로 답을 구한다. 그렇다면 $k=5$인 경우에는 어떤 식이 나올까? $n^0 + n^1 + .... + n^{k - 1} < n^k$ 이라는 사실을 안다면 알수 있을 것이다. 바로 $3^0 + 3^2$ 이다.

여기까지만 보면 그냥 단순한 수의 나열이 아닌가? 라고 대수롭게 생각을 할 수 있다. 그런데, 코드포스 문제를 조금 풀어보면서 이런 제곱수가 나오는 형태의 문제는 비트와 관련된 문제라고 생각하면 좋다. 그러면 $k=1$을 2진수로 나타내면 뭘까? $01$이다. $k=2$는 $10$이다. 마찬가지로 $k=3$ 은 $11$, $k=4$는 $100$이다. 마지막으로 $k=5$ 는 $101$이다. 이렇게 $k$를 2진수로 나타내보면 어떻게 풀지 감이 올 것이라고 생각한다.

$k = 3$의 2진수 표현인 $11$을 보면 이에 대응되는 식은 $3^0 + 3^1$ 이다. 그러면 이진수 비트가 $1$이면 그에 대응되는 이진수 자리를 더하면 어떨까? 만약 $k = 10$ 이면 $1010$이고, 맨 앞에 있는 비트 1은 2의 3승 자리기 때문에 문제에는 2대신에 $n$의 3승을 더하는 것이다. 그렇다면 $3^3 + 3^1 = 28$ 이 $k=10$의 답이 될 것이다.

즉 $k$를 2진수로 표현할 때 비트 $1$에 대응되는 자리를 $n$의 제곱승으로 표현해서 모든 수를 더하면 답이 나오게 될 것이다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

const int mod = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, k; cin >> n >> k;
        long long ans = 0, tmp = 1;
        while(k > 0){
            if(k & 1) ans = (ans + tmp) % mod;
            tmp = (tmp * n) % mod;
            k >>= 1;
        }
        cout << ans % mod << "\n";
    }
    return 0;
}