原题链接：

Problem - 1594B - Codeforces

题目描述

Theofanis really likes sequences of positive integers, thus his teacher (Yeltsa Kcir) gave him a problem about a sequence that consists of only special numbers.

Let's call a positive number special if it can be written as a sum of different non-negative powers of n">nn.

n">For example, for n=4">n=4, number 17">17 is special, because it can be written as 40+42=1+16=17">4^0+4^2 = 1 + 16 = 17,  but 9">9 is not.

Theofanis asks you to help him find the k">kk-th special number if they are sorted in increasing order.

k">Since this number may be too large, output it modulo 109+7">10^9+7.

k">109+7">输入

The first line contains a single integer t">tt (1≤t≤104">1 ≤ t ≤ 10^4) — the number of test cases.

The first and only line of each test case contains two integers n">nn and k">kk (2≤n≤109">2 ≤ n ≤ 10^9; 1≤k≤109">1 ≤ k ≤ 10^9).

n">k">2≤n≤109">1≤k≤109">输出

n">k">2≤n≤109">1≤k≤109">For each test case, print one integer — the k">kk-th special number in increasing order modulo 109+7">10^9+7.

n">k">2≤n≤109">1≤k≤109">k">109+7">输入样例

3
3 4
2 12
105 564

n">k">2≤n≤109">1≤k≤109">k">109+7">输出样例

9
12
3595374

n">k">2≤n≤109">1≤k≤109">k">109+7">分析及代码实现

n">k">2≤n≤109">1≤k≤109">k">109+7">题目要求寻找 由n的非负指数的数及他们任意的和的数组（升序排列）的第k个数字

n">k">2≤n≤109">1≤k≤109">k">109+7">很难发现，k的二进制形式中的1其实就表示累加了以该位次为幂的底数的值。

• n">k">2≤n≤109">1≤k≤109">k">109+7">比如n为3，k为13，此时k的二进制为1101。
• n">k">2≤n≤109">1≤k≤109">k">109+7">那么第k个以n为底的幂底数的累加就为3^0 + 3^2 + 3^3 = 3

那么我们就可以写出n = 3时的情况

n">k">2≤n≤109">1≤k≤109">k">109+7">

 c++代码实现

#include
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;

int main(){
    int t;
    cin >> t;
    while(t--){
        ll n, k, ret = 0, deal = 1;
        scanf("%lld%lld", &n, &k);
        while(k){
            if (k & 1)//如果当前最后一位是1，则加上deal
                ret = (ret + deal) % mod;
            deal = deal * n % mod;//处理deal
            k >>= 1;//右移一位，看k的下一个二进制位
        }
        printf("%lld\n", ret);
    }
    return 0;
}