2019-10-11 AtCoder Beginner Contest 142 D - Disjoint Set of Common Divisors 問題概要 正整数の正の公約数の集合から任意の2つについて互いに素になるように要素を選ぶ時の要素数の最大値を求めよ。 atcoder.jp 解法 まず、の公約数を全列挙する。これはのgcdの約数であるからgcdを求めた後にで求められる。 この中から任意の2要素が互いに素となるように選ぶためには、素数である要素を選べばよいから、先ほど求めた集合を順に見ていくことで答えとなる数が求まる。 atcoder.jp
の正の公約数の集合から任意の2つについて互いに素になるように要素を選ぶ時の要素数の最大値を求めよ。の公約数を全列挙する。これはのgcdの約数であるからgcdを求めた後に
で求められる。