#1983. 普罗达科特
普罗达科特
普罗达科特
题目描述
标题: 普罗达科特 - Problem - QOJ.ac
#4264. 普罗达科特
The problem was used in the following contests:
令 N=∏ni=1paii,M=∏ni=1pbii,其中 pi 是两两不同的素数。
求将 N 表示成 k 个正整数的乘积的方案数,也就是 N=∏ki=1xi 的解的个数,答案对 109+21 取模。
对于子问题 1,要求对于所有整数 i 满足 1≤i<k,都有 xi<xi+1。
对于子问题 2,要求对于所有整数 i 满足 1≤i<k,都有 xi≤xi+1。
对于两个子问题都要求对于所有整数 i 满足 1≤i≤k 都有 xi∤M,即 xi 不是 M 的约数。
输入格式
第一行两个正整数 n,k。
接下来一行 n 个非负整数,第 i 个整数表示 ai。
接下来一行 n 个非负整数,第 i 个整数表示 bi。
输入中没有给出 p1,…,pn,显然 pi 的取值并不影响答案。
输出格式
一行两个整数,分别表示子问题 1 和 2 的答案。
样例一
input
5 3
5 5 4 5 5
3 0 3 2 3
output
295164 295326
样例二
input
10 5
13 11 17 7 9 2 11 11 10 12
7 9 4 15 18 4 9 7 4 2
output
75340090 59089865
限制与约定
共 10 个测试点,只有子问题 1 答案正确将获得 3 分,只有子问题 2 答案正确将获得 6 分,都正确将获得 10 分。
测试点编号 n ai bi k 1≤5≤5≤5≤32≤10≤20≤20≤53=1≤1018≤1018≤254≤50≤103=0≤205≤1018≤256≤103≤103≤107≤1018≤1018≤108≤159≤2010≤25
**时间限制:**3s
**空间限制:**256MB
来源
中国国家集训队互测2015 - By 杜瑜皓
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 3
5 5 4 5 5
3 0 3 2 3
295164 295326
样例 2
10 5
13 11 17 7 9 2 11 11 10 12
7 9 4 15 18 4 9 7 4 2
75340090 59089865