Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、11問目を解説していきたいと思います。
問題名 【D – Disjoint Set of Common Divisors】
入力
A ： 正整数
B ：正整数
考察
今回の問題は、手を動かしてみると意外と難しかったりします。
理由としては、公約数を出した後、いくつかの公約数を選択しそのすべてがお互いに素でないといけないためです。
ではどうするか？
今回大事なのは、選ばれた数2つがお互いに素であり、かつAとBの公約数ということです。
なので、はじめにAとBの公約数を求めるのではなく、AとBに対しそれぞれ素因数分解を行います。
その後、得られたAの素因数とBの素因数の共通している部分を抽出します。
抽出された数字は、素数なのでどの2つの数字を選んでもお互いに素になりますし、お互いの約数であることは自明です。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
A,B = MI()
def tameshi(n):#試し割り法というN<10^12のときに使える素因数分解する手法
ret = []
for i in range(2, int(n ** (1 / 2)) + 1):
if i > n:break
while n % i == 0:
n //= i
ret.append(i)
if n != 1:
ret.append(n)
return ret
a = tameshi(A)#Aの約数
b = tameshi(B)#Bの約数
a.append(1)#aに1を追加
a = list(set(a))
b.append(1)
# print(a,b)
kouyaku = []#公約数を集めるリスト
for i in range(len(a)):#aというAの約数をまとめた約数において
if a[i] in b:#その値がbに含まれるのなら
kouyaku.append(a[i])
print(len(kouyaku))まとめ
数学チックな問題は、気がつけると一瞬で解けるので、本番も得点源にしていきたい！
コメント