[백준 06030] Scavenger Hunt [Python]

 

 

문제

Farmer John has scattered treats for Bessie at special places in the pasture.  Since everyone knows that smart cows make tasty milk, FJ has placed the treats at locations that require Bessie to think. He has given her two numbers, P and Q (1 <= P <= 6,000; 1 <= Q <= 6,000), and she has to check every point in the pasture whose x-coordinate is a factor of P and whose y-coordinate is a factor of Q to find her treat.

Suppose FJ gives Bessie P = 24 and Q = 2. Here are all of their respective factors:

• P = 24 => 1, 2, 3, 4, 6, 8, 12, 24
• Q = 2 => 1, 2

Bessie would thus check grid locations: (1, 1), (1, 2), (2, 1), (2, 2), (3, 1)...

Help Bessie by printing all of the points she ought to check.

입력

• Line 1: Two space separated integers: P and Q

 

출력

• Lines 1..?: A complete list of unique pairs of space-separated integers sorted by the first number and, if tied, the second number: a factor of P followed by a factor of Q

---

 풀이

주어진 P와 Q의 약수들로 이루어진 product을 출력하면 된다.

P, Q의 크기가 작으므로 선형 탐색으로 약수를 구해도 충분하다.

product을 사용해도 되고 중첩 반복문을 통해 출력해도 된다.

---

소스코드

보기

---

출처

https://www.acmicpc.net/problem/6030