Description给出n个正整数：a1,a2,a3,…,an.m表示这n个数的乘积.求：把m分解成n个正整数相乘,有多少种分法.（注：分解出的这n个数是有序的,如：1,2和2,1是两种不同的分法）Input第一行输入t,代表

Question

Description
给出n个正整数：a1,a2,a3,…,an.
m表示这n个数的乘积.
求：把m分解成n个正整数相乘,有多少种分法.
（注：分解出的这n个数是有序的,如：1,2和2,1是两种不同的分法）
Input
第一行输入t,代表有t组测试数据.（t

Answer 1

这个解释不是为了15分,是为了努力学习acm的你而写的：
这个应该算是初级的数论问题吧,首先我们遇到这一类的问题的时候,一定注意素因数是一切这一类问题的基本解法.所以第一步想都不用想,把这些给出来的n个数据一个一个的分解质因数,至于怎么分解,完全平方也好,椭圆曲线也好,随便吧反正是大约log(n)的单个分解复杂度,所以500个数据不会超时.
然后我们把分解的结果分类,像这样,假如给你的数字是4,8,9三个,结果就是5个2,2个3,(4分解成2个2,8分解成3个2,9分解成2个3),那么最后凑出来的结果们就是用这些5个2,2个3,凑出来的结果了.
接下来就很简单啦,一共n个数,就是把这些质因数分组.用这个例子来说的话,就是把5个2,2个3,分成三组.举个例子,我们可以第一组取0个2,0个3,也就是这个组是1,第二组取一个2,1个3,也就是这个组是6,剩下的一定是4个2和1个3,也就是16*3=48,明白我意思了吗?
所以现在成了一个排列组合的问题,把每个数字的组分成n份,每份可以为0,最后分的结果乘起来就是最终的结果.这个不用我多说了吧,隔板什么的挺简单的.
最后就是这个小小的技巧,上一步说道要把分了的结果乘起来,可是可能会溢出,这个时候一边乘一边取模就可以了.不会影响最终结果.
PS：我搞acm的时候就是数论选手,加油!