[BOJ/Math]9613:GCD合計

15077 ワード
アルゴリズム#アルゴリズム# テキストリンク

のり

from itertools import combinations
import sys
import math

input = sys.stdin.readline
result = list()

t = int(input())

for i in range(t):
  sum = 0
  numbers = list(map(int, input().split()))
  del numbers[0]
  
  for x, y in combinations(numbers, 2):
    gcd = math.gcd(x, y)
    sum += gcd
      
  result.append(sum)

for i in range(t):
  print(result[i])
.
.
.

💡 ユークリッドアーク法とgcd,lcm

  • 最大公約数=gcd=最大公因子
    最小公倍数=lcm=最小公倍数
  • 本題は数学ライブラリを用いてgcdを取得する.
    下図に示すように、gcd、lcmはユークリッドアーク法で直接求めることができる.
    • .

    #ユークリッド護法、GCD


    ユークリッドアーク除去法:2つの整数aとb(a>b)がある場合、a=bq+r(0<=r(aとbの最大公約数)=(bとa%bの最大公約数).
    ∴ gcd(a, b) = gcd(b, r)
    rが0である場合、a,bの最大承諾数はbである.
    ⑪a%b=0はgcd(a,b)=bを表す
    .

    #LCM-GCD


    a,bの最小公倍数は、a*bをa,bで割った最大公約数である.
    ∴ lcm(a, b) = a b//gcd(a, b)*
    .
    コード:
            def gcd(a, b):
        	if b == 0:
        		return a
        	else:
        		return gcd(b, a % b)
        
        def lcm(a, b):
          return a * b // gcd(a, b)
    .
    .
    .

    itertoolsライブラリの配列(シーケンス)、組合せ(組合せ)クラス

  • シーケンスvs組合せ
    高校時代に並べ替えや組み合わせを習った記憶を思い起こすと、並べ替えは順序を考慮し、組み合わせは順序を考慮しない.順序、組合せ、繰返し順序、繰返し組合せの使用方法については、次のブログを参照してください.
    (Python)シーケンス、コンビネーション、重複シーケンス、重複コンビネーションを容易に実現という問題では,各試験例に所定の数字からなるgcdのペアが必要であるため,順序を考慮しない組合せクラスを用いた.
    .
  • for文+組合せ(組合せ)最適化:2 Dリスト/凡例から内部要素にアクセス

  • 2 Dリストで内側リストの要素にアクセスする場合、通常はa[0][0]という方法が使用されます.

  • 2 Dリストでは、内側リストのサイズが同じで、サイズが小さい場合は、for文を次のように書くことで、内側リストの要素に直接アクセスできます.

  • forとinの間で使用される変数は、内側リストのサイズがnの場合、n個が使用されます.

  • 二次元図、リストに図がある場合や図の中に図がある場合も同じです!

  • 例)
    >>> a = [[10, 20], [30, 40], [50, 60]]
>>> for x, y in a:    # 리스트의 가로 한 줄(안쪽 리스트)에서 요소 두 개를 꺼냄
...     print(x, y)
...
10 20
30 40
50 60

  • この問題への応用
    実際,組合せ,配列の結果は2次元リストではなくクラスであるため,リストに変換して使用する必要があるが,変換しなくてもこのような使用の正確な原理は分からない.
    for i in range(t):
  sum = 0
  numbers = list(map(int, input().split()))
  del numbers[0]
  
  for x, y in combinations(numbers, 2):
    gcd = math.gcd(x, y)
    sum += gcd
      
  result.append(sum)
  • 再包装前コード
    for i in range(t):
  sum = 0
  numbers = list(map(int, input().split()))
  del numbers[0] 

  combs = list(combinations(numbers, 2))
  for j in range(len(combs)):
    gcd = math.gcd(combs[j][0], combs[j][1])
    sum += gcd

  result.append(sum)

  • 注意:次のコードに示すように、forとinの間に変数を書くだけで、自分にアクセスできます.

  • 中のリストの各要素に近づく必要がない場合は、このようにします.
    from itertools import combinations

for i in combinations([1,2,3,4], 2):
    print(i, end=" ")

>> 결과: (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)
    • struct集合
    位置検索マップアプリケーション