ABC170 D - Not Divisible

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = sorted(il())

    cnt = collections.Counter(A)
    multiple = set()
    ret = 0
    maximum = max(A)
    for a in A:
        # 約数を既に使用済みの場合はcontinue
        if a in multiple:
            continue

        # 約数がなく、
        # 同じ数字が存在しない場合には
        # 条件に一致する整数
        if cnt[a] == 1:
            ret += 1

        i = 1
        # 整数の倍数を列挙
        while a * i <= maximum:
            multiple.add(a*i)
            i += 1
    print(ret)


if __name__ == '__main__':
    main()

考え方

整数列Aから値の小さい順に、条件に一致するか否かを確かめ、
エラトステネスの篩と同様のやり方で倍数を列挙する。

エラトステネスの篩 - Wikipedia

整数列Aの最も小さい値は、同じ値がなければほかの数字で割り切ることができないため、
整数列Aをソートし、小さい値から順に探索を行なう。
確かめるべきは、

• 既に使用した整数の倍数であるか否か
• 同じ整数が整数列Aに存在するか否か

の2点を確認する。

どちらの条件にも当てはまらない場合には、
指定された条件に一致した他の整数で割り切ることが出来ない整数とする。
また、条件に一致する整数が存在した場合、その値で割り切ることができる整数を全て列挙する。

これはエラトステネスの篩と同様の考え方で、
割り切ることのできない整数(a)が存在した場合、
その倍数(2 * a, 3 * a)は必ず割り切ることのできない整数(a)で割り切ることができるため。