ABC142 D - Disjoint Set of Common Divisors
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time # 時々使う # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from decimal import Decimal # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 INF = float('inf') def make_divisors(n): lower_divisors, upper_divisors = [], [] i = 1 while i*i <= n: if n % i == 0: lower_divisors.append(i) if i != n // i: upper_divisors.append(n//i) i += 1 return lower_divisors + upper_divisors[::-1] # 注意: 1 を素数として判定する def isPrime(N): for n in range(2, int(N ** 0.5) + 1): if N % n == 0: return False return True def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") A, B = il() a_div = set(make_divisors(A)) b_div = set(make_divisors(B)) common_div = a_div & b_div cnt = 0 for c in common_div: if isPrime(c): cnt += 1 print(cnt) if __name__ == '__main__': main()
考え方
公式解説では様々な回答方法が記載されていますが、
本回答では公約数を全て求めて、公約数の中に存在する1と素数をカウントしました。
- 回答概要
- 集合を用いて、公約数を求める
- 公約数の中から1と素数の数をカウントする
公約数の中から互いに素となる整数について考えます。
ある整数x, y
が互いに素であるということは、
x, y
の最大公約数が1
の状態にあります。
1
以外の整数が公約数に存在しない整数は素数と1
なので、
A
とB
の公約数から1
と素数の数を数えます。
A
とB
の公約数を求めるために、集合を用います。
A
の公約数の集合とB
の公約数の集合から論理積を求めることで、
A
とB
に共通する公約数を求めます。
あとは共通する公約数から上記の1
と素数の数を数えることで回答することが出来ます。