發表新討論
#30899: python 使用字典、集合


Akira_chi (unknown)

學校 : 不指定學校
編號 : 194818
來源 : [59.120.185.108]
最後登入時間 ：
2022-06-24 14:55:58
a024. 最大公因數(GCD) | From: [59.120.185.108] | 發表日期 : 2022-06-20 16:43

非快速解，純分享作法

  1. 建立字典紀錄因式分解的結果，key=質因數, value=次方數
  2. 把兩個字典的key找出來並轉為集合
  3. 求出兩個集合的交集(公因數)
  4. 再由公因數去找出各自最小次方數，乘起來

 

Getfactor(x) : 找出X的質因數分解並建成字典後回傳

for x in a:
        fact_Matrix.append(Getfactor(x))
    #print (fact_Matrix)

    for i in fact_Matrix:
        key_Matrix.append(set(i.keys()))
    inter_section = key_Matrix[0] & key_Matrix[1]

    base = list(inter_section)

    Sum = 1
    for x in base:
        Sum *= x**min(fact_Matrix[0].get(x), fact_Matrix[1].get(x))
    print(Sum)
 
ZeroJudge Forum