【题解】StarryCoding P207 特别的多项式

题目传送门：P207 特别的多项式 | StarryCoding算法竞赛平台

题目描述

P i p e r Piper Piper近日又开始研究上了多项式，但是这次 P i p e r Piper Piper研究的多项式并非普通的多项式了。

我们知道，一元 n n n次多项式可以用如下的表达式来表示：

f ( x ) = a n x n + a n − 1 x n − 1 + … + a 1 x + a 0 , a n ≠ 0 f(x) = a_nx^n + a_{n - 1}x ^ {n - 1} + \ldots + a_1x + a_0, a_n \neq 0 f(x)=an​xn+an−1​xn−1+…+a1​x+a0​,an​=0

其中 a i x i a_ix^i ai​xi称为 i i i次项， a i a_i ai​称为 i i i次项的系数。

为了有趣一些， P i p e r Piper Piper规定：一个由不同非负整数组成的数组 b b b，由这个数组 b b b中所有元素得到一个多项式，其中 b i b_i bi​次项的系数为 1 1 1，将一个正数 n n n代入这个多项式得到的计算结果是特殊数。

换句话说，如果一个正数可以写成 n n n 的不同非负幂的和，我们就称它为特殊数。例如，对于 n = 4 n = 4 n=4 来说，数字 17 17 17 是特殊的，因为它可以写成 4 0 + 4 2 = 1 + 16 = 17 4^0 + 4^2 = 1 + 16 = 17 40+42=1+16=17 ，但 9 9 9 不是。

但是 P i p e r Piper Piper懒惰的毛病又犯了，可是他又想快速地找到按递增顺序排列的 k k k 这个特殊的数字。请你写个程序来帮助 P i p e r Piper Piper。因为这个数可能太大，所以输出它的模数 1 0 9 + 7 10^9+7 109+7 。

输入描述

第一行包含一个整数 t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104 ) - 测试用例数。

每个测试用例的第一行，也是唯一一行，包含两个整数 n n n 和 k k k （ 2 ≤ n ≤ 1 0 9 2 \le n \le 10^9 2≤n≤109 ; 1 ≤ k ≤ 1 0 9 1 \le k \le 10^9 1≤k≤109 ）。

输出描述

对于每个测试用例，打印一个整数–以 1 0 9 + 7 10^9+7 109+7 为模数依次递增的 k k k -th 特殊数。

输入样例1

3
3 4
2 12
105 564

输出样例1

9
12
3595374

样例解释

对于第一组测试样例： n = 3 n = 3 n=3时的递增序列为： [ 1 , 3 , 4 , 9 … ] [1, 3, 4, 9 \ldots] [1,3,4,9…]，第四个数字为 9 9 9。

思路

对于大于 2 2 2的 n n n， n x + 1 2上面规则同样适用。所以可以将 k k k用二进制的方式表示出来，然后将 k k k的二进制上的 1 1 1乘上对应 n n n的幂次即可得到答案。

代码

#include
using namespace std;
using ll = long long;
const int p = 1e9 + 7;
void solve()
{
    ll n, k; cin >> n >> k;
    ll temp = 1;
    ll ans = 0;
    for(int i = 0; i