#20216: 解法思路


p3a_owhj (阿普二信)

學校 : 不指定學校
編號 : 39897
來源 : [36.227.79.178]
最後登入時間 :
2024-06-04 22:09:36
d741. 复制贴上——加强版 -- d304: 复制贴上 加强版 | From: [220.137.1.3] | 發表日期 : 2019-12-14 02:31

質數 p 的按鈕次數一定是 p 次 例如 3 一定CVV、 5一定 CVVVV
所以只要求出 N = p1*p2*p3*...pk {pi<=pj,for i<j} ,最少的按鈕數即 所有pi的和
如果沒有2個2的話就很簡單了, 只要算出 {p1,p2,...,pk}的排列數即可
例如 50 = 2*5*5 ,其排列數為 255,525,552 共3 way
       30 = 2*3*5, 其排列數為 235,253,325,352,523,532 共6 way

 
=======
但若有2個2的話,可以合成一個4,其按鍵數相同,所以也要算每2個2換成一個4的情形
例如 36 = 2*2*3*3, 需求{2,2,3,3}的排列數 + {3,3,4}的排列數 6+3共 9 way
又若 80 = 2*2*2*2*5,需求{2,2,2,2,5}+{2,2,4,5}+{4,4,5}三個排列數的和 共 20 way

 
ZeroJudge Forum