摘要
Title: 1295. X的因子链
Tag: 素因子分解、组合计数、多重集的排列数问题
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1295. X的因子链

• 题意

  输入正整数 X，求 X 的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。

• 思路

  首先想到的是素因子分解，得到结果后，可以看出最长的链，就是素因子依次乘过去，比如 $100 -> 2, 2, 5, 5$，那么最长链之一就是$2, 4, 20, 100$

  其次，存在相同元素，那么用总的组合数除以各类的组合数即可，即多重集的排列数问题

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-31 20:40:38
  FilePath: \ACM\Acwing\1295.py
  LastEditTime: 2022-03-31 20:40:39
  '''
  from math import factorial as fact
  from collections import Counter
  while True:
      try:
          n = int(input())
          a = []
          cnt = 0
          d = Counter()
          i = 2
          while i <= n // i:
              if n % i == 0:
                  a.append(i)
                  while n % i == 0:
                      d[i] += 1
                      cnt += 1
                      n //= i
              i += 1
          if n > 1:
              a.append(n)
              cnt += 1
              d[n] += 1
  
          ans = fact(cnt)
          for key in d.keys():
              ans //= fact(d[key])
          print(cnt, ans)
      except:
          break