バックアップ・アルゴリズムの手順13(整数論と組合せ論)

新規コンテンツ

1）5086号排水と薬液

import sys

while True:
    a, b = list(map(int, sys.stdin.readline().split()))
    if a == 0 and b == 0:
        break

    if a % b == 0 and a > b:
        print('multiple')
    elif b % a == 0 and b > a:
        print('factor')
    else:
        print('neither')

2）1037号ミネラルウォーター

特定値Nの薬水の個数と本物の薬水を入力します.
薬水たちは昇順に並べたときに対称構造を形成する点を利用した.
したがって、ソートされた約数リストの最初の要素と最後の要素にN値を乗算します.

N = int(input())
nums = list(map(int, input().split()))
nums.sort()

ans = nums[0] * nums[-1]
print(ans)

3)1609回の最大公倍数(gcd)と最小公倍数(lcm)

最大公約数と最小公約数を求める方法を検索したところ、Pythonのmathモジュールで関数が1つ実現したので、すぐに使ったという.

import math

a, b = list(map(int, input().split()))

# 최대 공약수 math 모듈의 gcd() Greatest Common Divisor

# 최소 공배수 math 모듈의 lcm() Least Common Multiple
# 최소 공배수는 두 수의 곱을 최대 공약수로 나눠준 값과 동일하다.

print(math.gcd(a, b))
print(math.lcm(a, b))

しかし学習の立場なので、得られたヒントで一般コードも書いてあります.
次のコードは、入力値の小さな値の範囲で文を繰り返し、最大承諾数を求めます.最大公約数が1の場合を考えて、1から!

import math

a, b = list(map(int, input().split()))
gcd = 0
lcm = 0

# b의 범위에서 반복문을 돌며 a를 나눠봄으로써 최대 공약수 구하기.
if a > b:
    for i in range(1, b+1):
        if a % i == 0 and b % i == 0:
            gcd = i
else:
    for i in range(1, a+1):
        if a % i == 0 and b % i == 0:
            gcd = i

# 최소 공배수는 두 수의 곱을 최대공약수로 나눈 값이다.
# 따라서 몫을 구하는 // 연산자
lcm = a * b // gcd

print(gcd)
print(lcm)

4)1934号最小公倍数(ユークリッドアーク除算)

ユークリッド号製法とは何ですか。

すなわち、a%b(aをbで割ったもの)およびbの最大承諾数は、数字aおよびbがある場合、aおよびbの最大承諾数に等しい.
したがって、繰り返し文により、aにb値、bにa%b値が加算され、bが0になるまで、a値が0に繰り返すと、a値は最大公約数となる.
さらに、最小公倍数は、2つの数の積を最大公倍数で割ったものであるので、簡単な演算で求めることができる.
第三題私の解答は不要な薬水に関わり、時間の複雑さを増したが、ユークリッドアーク除去法の理論を用いることで複雑さを大幅に低減することができる.

import sys

# 유클리드 호제법 활용!
def getGcd(a, b):
    # b가 0이 될 때 까지 (0은 false이기 때문에 자동 종료)
    while b:
        a, b = b, a%b
    return a

T = int(input())
for i in range(T):
    a, b = map(int, sys.stdin.readline().split())

    gcdVal = getGcd(a, b)
    lcmVal = a * b // gcdVal

    print(lcmVal)

5）2981号検査

❌❌❌❌<第1話最終失敗!->コードのコメントと理解に注目>
注意:https://tmdrl5779.tistory.com/94
これは数学の知識が必要な問題です.
入力した値を以下のように分離し、Mを目標とする.
A = M a + R
B = M b + R
C = M * c + R
ここでRをクリアすると
A - B = M ( a - b )
B - C = M ( b - c )
同じ式と同じで、Mはこれらの要素の差の約数です.
したがって、差分値リストを作成すると、関連する要素の最大公数をループして検索し、最大公数の約数を出力します.
このとき、最大公約数の約数を求める場合、
18%2=0(2=約)
18/2=9(9=約)
上記のように、2つずつ増加します.平方根の複雑さを減らすことができます…!!

from math import gcd
from math import sqrt

n = int(input())
ns = list(int(input()) for _ in range(n))
ns.sort()
interval = list()
ans = list()

# 입력값들의 차이값을 저장하는 리스트
for i in range(1, n):
    interval.append(ns[i] - ns[i - 1])

# 차이값 리스트를 돌며 이전 원소와의 최대공약수(gcd)를 구함
prev = interval[0]
for i in range(1, len(interval)):
    prev = gcd(prev, interval[i])

# 마지막으로 출력된 최종 최대공약수의 약수를 구한다.
# 이 때 제곱근 까지만 검색하여, i뿐만 아니라 몫도 저장하는 것이 포인트!
for i in range(2, int(sqrt(prev)) + 1): #제곱근까지만 탐색
    if prev % i == 0:
        ans.append(i)
        ans.append(prev//i)
ans.append(prev)
ans = list(set(ans)) #중복이 있을수 있으니 제거
ans.sort()
print(*ans)

6）3036号リング

最初の与えられた円の半径と残りの円の半径との間の最大公因数を見つけ、既約分数形式で表した.

from math import gcd

N = int(input())
nums = list(map(int, input().split()))

first = nums[0]
for i in range(1, N):
    gcdVal = gcd(first, nums[i])
    print(str(first//gcdVal) + '/' + str(nums[i]//gcdVal))

7）11050次二項係数1

最初は再帰関数でファクトリを実現したが,再帰エラーが発生した.BOJ採点時、復帰は1000回に制限されたという.
したがって,再帰関数ではなく反復文でファクトリ化を実現した.

N, K = map(int, input().split())

def factorial(n):
    ans = n
    while True:
        if n <= 2:
            return ans
            break
        ans *= (n-1)
        n -= 1

# nCn과 nC0은 1로 약속
if N == K or K == 0:
    print(1)
else:
	# 이항계수 구하는 식
    print(factorial(N)//(factorial(K)*factorial(N-K)))

8）11051次二項係数2

上と同じコードを使用しました.すなわち,DP理論を利用したコードはない.

N, K = map(int, input().split())

val = 0
def factorial(n):
    ans = n
    while True:
        if n <= 2:
            return ans
            break
        ans *= (n-1)
        n -= 1

if N == K or K == 0:
    val = 1
else:
    val = factorial(N)//(factorial(K)*factorial(N-K))

print(val % 10007)

+)動的計画法(DP)

小分類でダイナミックプランニング法と書かれていたのでDPを学びました.
動的計画法の典型的な例はフィボナッチ数列である.
フィボナッチ数列が再帰関数として表されると、いくつかの次の数値が繰り返し書き込まれ、関数が呼び出され続けます.
これを防止するために、呼び出された値を配列から取り出すのではなく、値を格納する配列を作成することでパフォーマンスを向上させることができます.
次のコードは、パスカルの三角形値を格納するために2次元配列を生成するコードです.
これにより、nCk=n−1 Ck−1+n−1 Ckを実現することができ、演算速度を向上させることができる.

n, k = map(int, input().split())
# dynamic programming -> 중복 호출하는 값들을 배열에 저장함으로써 효율 up!
dp = [[0] * 1 for i in range(1001)]
dp[1].append(1)
for i in range(2, 1001):
    for j in range(1, i + 1):
        if j == 1:
            dp[i].append(1)
        elif j == i:
            dp[i].append(1)
        else:
            dp[i].append(dp[i - 1][j - 1] + dp[i - 1][j])
print(dp[n + 1][k + 1] % 10007)