問題
要約
- 正整数A, Bが与えられる。
- AとBの正の公約数の中からいくつかを選ぶ。
- 選んだ整数のうち、どの2つの異なる整数も互いに素でなければならない。
- 上記の条件を満たしながら、最大でいくつの整数を選べるかを求める。
既存投稿一覧ページへのリンク
解法手順1
AとBの最大公約数を求め、その最大公約数の素因数分解を行うことで、条件を満たす最大の整数の集合を得ることができる。
解法の手順
- 入力された正整数AとBの最大公約数（GCD）を求める。
- 得られた最大公約数を素因数分解する。
- 素因数分解で得られた素因数と1を含む集合を作成する。
- 集合の要素数を出力する。
実装手順
- ユークリッドの互除法を使用してAとBの最大公約数を計算する。
- 最大公約数を変数max_divに格納する。
- 答えを格納するための集合ansを作成し、1を追加する。
- max_divが1より大きい間、以下の処理を繰り返す：
a. 2からmax_divの平方根まで順に割り切れる数iを探す。
b. 割り切れる数iが見つかった場合、max_divをiで割り、iをansに追加する。
c. 割り切れる数が見つからなかった場合、max_div自体が素数なので、ansに追加し、max_divを1にする。 - 最後に、ansの要素数（len(ans)）を出力する。
ACコード1
ac.py
def io_func():
# 標準入力から2つの整数を受け取る
return map(int, input().split())
def gcd(a, b):
# ユークリッドの互除法でGCDを計算
while b:
a, b = b, a % b
return a
def solve(a, b):
# AとBの最大公約数を計算
max_div = gcd(a, b)
# 答えを格納するための集合を作成し、1を追加
ans = set()
ans.add(1)
# max_divが1より大きい間、素因数分解を行う
while max_div > 1:
flg = True
# 2からmax_divの平方根まで順に割り切れる数を探す
for i in range(2, int(max_div ** 0.5) + 1):
if max_div % i == 0:
max_div //= i
ans.add(i)
flg = False
break
# 割り切れる数が見つからなかった場合
if flg:
ans.add(max_div)
max_div = 1
# 集合の要素数を出力
print(len(ans))
# メイン処理
a, b = io_func()
solve(a, b)
###
# a, b: 入力された2つの正整数
# max_div: AとBの最大公約数
# ans: 条件を満たす整数の集合
# flg: 素因数が見つかったかどうかを示すフラグ
# i: 素因数の候補
# 1. io_func関数: 標準入力から2つの整数を受け取る
# 2. gcd関数: ユークリッドの互除法を用いて最大公約数を計算する
# 3. solve関数: 主な処理を行う
# 3.1. AとBの最大公約数を計算
# 3.2. 答えを格納するための集合を作成し、1を追加
# 3.3. 最大公約数が1より大きい間、以下の処理を繰り返す
# a. 2から最大公約数の平方根まで順に割り切れる数を探す
# b. 割り切れる数が見つかった場合、その数を集合に追加し、最大公約数を更新
# c. 割り切れる数が見つからなかった場合、最大公約数自体を集合に追加
# 3.4. 集合の要素数を出力
# 4. メイン処理: io_func関数で入力を受け取り、solve関数を呼び出す
オブジェクト指向版1
ac_object.py
from abc import ABC, abstractmethod
from typing import List, Set
class InputReader(ABC):
@abstractmethod
def read_integers(self) -> List[int]:
pass
class ConsoleInputReader(InputReader):
def read_integers(self) -> List[int]:
# 標準入力から2つの整数を受け取る
return list(map(int, input().split()))
class MathOperations:
@staticmethod
def gcd(a: int, b: int) -> int:
# ユークリッドの互除法でGCDを計算
while b:
a, b = b, a % b
return a
class PrimeFactorizer:
@staticmethod
def factorize(n: int) -> Set[int]:
factors = set()
factors.add(1) # 1は常に因数
# nが1より大きい間、素因数分解を行う
while n > 1:
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
factors.add(i)
n //= i
break
else:
factors.add(n)
break
return factors
class GCDFactorSolver:
def __init__(self, input_reader: InputReader, math_ops: MathOperations, factorizer: PrimeFactorizer):
self.input_reader = input_reader
self.math_ops = math_ops
self.factorizer = factorizer
def solve(self) -> int:
# 入力を読み取る
a, b = self.input_reader.read_integers()
# AとBの最大公約数を計算
max_div = self.math_ops.gcd(a, b)
# 最大公約数を素因数分解
factors = self.factorizer.factorize(max_div)
# 因数の数を返す
return len(factors)
class ResultPrinter:
@staticmethod
def print_result(result: int):
print(result)
# メイン処理
def main():
input_reader = ConsoleInputReader()
math_ops = MathOperations()
factorizer = PrimeFactorizer()
solver = GCDFactorSolver(input_reader, math_ops, factorizer)
result = solver.solve()
ResultPrinter.print_result(result)
if __name__ == "__main__":
main()
オブジェクト指向版1で書くメリット
拡張性と再利用性
ac_object.py
import logging
class PrimeFactorizer:
def __init__(self):
self.logger = logging.getLogger(__name__)
self.logger.setLevel(logging.DEBUG)
handler = logging.FileHandler('prime_factorizer.log')
handler.setFormatter(logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s'))
self.logger.addHandler(handler)
def factorize(self, n: int) -> Set[int]:
self.logger.info(f"Starting factorization of {n}")
factors = set()
factors.add(1)
while n > 1:
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
factors.add(i)
n //= i
self.logger.debug(f"Found factor: {i}")
break
else:
factors.add(n)
self.logger.debug(f"Found prime factor: {n}")
break
self.logger.info(f"Factorization complete. Factors: {factors}")
return factors
テスト容易性
ac_object.py
import unittest
class TestPrimeFactorizer(unittest.TestCase):
def setUp(self):
self.factorizer = PrimeFactorizer()
def test_factorize_prime_number(self):
self.assertEqual(self.factorizer.factorize(17), {1, 17})
def test_factorize_composite_number(self):
self.assertEqual(self.factorizer.factorize(12), {1, 2, 3})
def test_factorize_one(self):
self.assertEqual(self.factorizer.factorize(1), {1})
def test_factorize_zero(self):
self.assertEqual(self.factorizer.factorize(0), {1})
可読性と保守性の向上
ac_object.py
class GCDFactorSolver:
def __init__(self, input_reader: InputReader, math_ops: MathOperations, factorizer: PrimeFactorizer):
self.input_reader = input_reader
self.math_ops = math_ops
self.factorizer = factorizer
def solve(self) -> int:
a, b = self.input_reader.read_integers()
max_div = self.math_ops.gcd(a, b)
factors = self.factorizer.factorize(max_div)
return len(factors)
このコードは、入力の読み取り、GCDの計算、素因数分解、結果の計算という一連の処理を明確に示しています。