#P3462. DZY Loves Math II
DZY Loves Math II
题目描述
给定一个正整数 。对每个询问的正整数 ,求有多少个非空的质数序列 满足
$$\sum_{i=1}^k p_i=n,\qquad \operatorname{lcm}(p_1,\ldots,p_k)=S.$$同一个质数可以出现多次。答案对 取模。
输入格式
第一行两个正整数 ,其中 是询问数量。接下来 行,每行一个正整数 。
输出格式
输出 行,每行一个整数,表示对应询问的答案对 取模的结果。
样例
30 3
9
29
1000000000000000000
0
9
450000036
数据范围
对于所有数据,,,。