79 lines
1.2 KiB
Markdown
79 lines
1.2 KiB
Markdown
# 拆分数列计数
|
||
|
||
## 题目描述
|
||
|
||
对于正整数 $x$ ，若长度为 $n$ 的整数序列 $a[1,2,...,n]$ 满足：
|
||
$$
|
||
\prod_{i=1}^n a[i] = x
|
||
$$
|
||
|
||
则称序列 $a$ 是 $x$ 的一个 $n$ 拆分序列，注意 $a[i]$ 可以为负。
|
||
|
||
现给定 $x,n$，求 $x$ 的不同 $n$ 拆分序列数量(对 `1e9 + 7` 取模)。
|
||
|
||
|
||
- 2个拆分序列 $a,b$ 不同，当且仅当存在下标 $i\in [1,n]$ 满足 $a[i]\ne b[i]$。
|
||
|
||
## 输入格式
|
||
|
||
第一行1个整数 $q$，代表有 $q$ 组询问
|
||
|
||
接下来 $q$ 行，每行2个整数 $x,n$，代表一组询问
|
||
|
||
## 输出格式
|
||
|
||
$q$ 行，每行1个整数代表答案 (对 `1e9 + 7` 取模)
|
||
|
||
## 样例 #1
|
||
|
||
### 样例输入 #1
|
||
|
||
```
|
||
3
|
||
6 3
|
||
4 2
|
||
1244 1241
|
||
```
|
||
|
||
### 样例输出 #1
|
||
|
||
```
|
||
36
|
||
6
|
||
303870674
|
||
```
|
||
|
||
## 样例 #2
|
||
|
||
### 样例输入 #2
|
||
|
||
```
|
||
2
|
||
12414 211234
|
||
12314 12141352435
|
||
```
|
||
|
||
### 样例输出 #2
|
||
|
||
```
|
||
690493918
|
||
924519003
|
||
```
|
||
|
||
## 提示
|
||
|
||
【样例解释】
|
||
|
||
$x=4,n=2$ 时，共有6种拆分序列 $[-4,-1],[-2,-2],[2,2],[4,1],[-1,-4],[1,4]$
|
||
|
||
【数据范围】
|
||
|
||
对于20%的数据，$q=1，x,n\le 10$
|
||
|
||
对于40%的数据，$q\le 100，x,n\le 100$
|
||
|
||
对于另20%的数据，$q=1，n\le 10^6$
|
||
|
||
对于80%的数据，$n\le 10^6$
|
||
|
||
对于100%的数据，$1\le q\le 10^5，1\le x\le 10^6, 1\le n\le 10^{16}$ |