【Description给出n个正整数:a1,a2,a3,…-查字典问答网
分类选择

来自林新的问题

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

  Description

  给出n个正整数:a1,a2,a3,…,an.

  m表示这n个数的乘积.

  求:把m分解成n个正整数相乘,有多少种分法.

  (注:分解出的这n个数是有序的,如:1,2和2,1是两种不同的分法)

  Input

  第一行输入t,代表有t组测试数据.(t

1回答
2020-06-14 20:06
我要回答
请先登录
刘丛民

  这个解释不是为了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的时候就是数论选手,加油!

2020-06-14 20:07:09

最新问答

推荐文章

猜你喜欢

附近的人在看

推荐阅读

拓展阅读

  • 大家都在看
  • 小编推荐
  • 猜你喜欢
  •