LCC '23 Contest 4 S1 - Common Interests

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Trent is trying to come up with a pickup line for his valentine, but is having trouble deciding on what to talk about! He could be generic, but there's no way that works, and he could talk about the little things, but then it might seem like he's too interested! Thus, pingu tells him to write down the first N things that come to mind that he could talk about.

While there may be no way to model Trent's brain in code, let's denote the integer A as everything Trent is interested in, and the integer B as everything his valentine is interested in. Factors of both A and B represent things that both Trent and his valentine are interested in. The N things that Trent wrote down can be represented as the N largest of these factors (the more generic, the higher the corresponding number).

Adhering to pingu's advice, can you find the N largest numbers that divide both A and B?

Constraints

Subtask 1 [40%]

1 \le A, B \le 10^6

1 \le N \le 10

Subtask 2 [60%]

1 \le A, B \le 10^{12}

1 \le N \le 10^3

Input Specification

The first and only line of input contains A, B, and N.

Output Specification

Output on a single line the N largest numbers that divide both A and B, ordered from least to greatest. If there are less than N factors that divide A and B, output all the factors, again from least to greatest.

Sample Input 1

24 18 4

Sample Output 1

1 2 3 6

Sample Input 2

25 100 5

Sample Output 2

1 5 25

Comments

There are no comments at the moment.