#P3861. 拆分
拆分
题目描述
给定一个整数 ,求将 分解为互不相同的不小于 的整数的乘积的方案数。答案模 。
输入格式
第一行一个整数 ,表示数据组数。
接下来 行,每行一个整数 ,意义如描述所述。
输出格式
一共 行,每行一个整数,表示答案。
提示
样例中,因为
所以答案为
对于 的数据,保证 为质数
对于 的数据,保证
对于 的数据,保证
对于 的数据, 保证
所有数据满足
给定一个整数 n,求将 n 分解为互不相同的不小于 2 的整数的乘积的方案数。答案模 998244353。
第一行一个整数 T,表示数据组数。
接下来 T 行,每行一个整数 n,意义如描述所述。
一共 T 行,每行一个整数,表示答案。
样例中,因为
688=2×4×86=2×8×43=2×344=4×172=8×86=16×43
所以答案为 6
对于 10% 的数据,保证 n 为质数
对于 20% 的数据,保证 2≤n≤104
对于 50% 的数据,保证 2≤n≤107
对于 100% 的数据, 保证 2≤n≤1012
所有数据满足 1≤T≤5