서로 나누어 떨어지는 자연수 집합

https://codeforces.com/contest/1796/problem/C

Problem - C - Codeforces

이 문제를 풀면서 본 조건이 자주 나오는 것 같아 정리해 두려고 한다.

물론 웰노운이다. 그냥 자동적으로 떠올릴 수 있도록 하기 위해서 글을 쓴다.

 

A set of positive integers S is called beautiful if, for every two integers x and y from this set, either x divides y or y divides x (or both).

 

위 조건이 주어졌을 때 가장 먼저 떠올려야 하는 것은 제곱수이다.

즉, 위 조건을 만족하는 집합은 \( a^x (x >= 0) \) 이다.

 

증명은 귀류법으로 간단히 할 수 있다.