GLCCDM

시간 제한1초메모리 제한1024 MB

요약
K개의 서로 다른 양의 정수의 최대공약수가 A, 최소공배수가 B가 되도록 하는 수열을 찾고, 불가능하면 -1을 출력한다.
난이도

보통10점 중 7점

유형
정수론, 수학, 그리디, 완전 탐색
정답자
아직 제출이 없습니다

문제

gcd⁡(d_1,⋯ ,d_K)=A,lcm⁡(d_1,⋯ ,d_K)=B\operatorname{gcd}(d\_1, \cdots, d\_K) = A, \operatorname{lcm}(d\_1, \cdots, d\_K) = B를 만족하는 서로 다른 양의 정수 KK개로 이루어진 수열 d_1,⋯ ,d_Kd\_1, \cdots, d\_K를 구해보자.

입력

첫 번째 줄에 양의 정수 AA, BB, KK가 공백을 사이에 두고 주어진다. (1≤A<B≤1,000,000;2≤K≤100)(1 \le A < B \le 1\\,000\\,000 ; 2 \le K \le 100)

출력

KK개의 양의 정수 d_1,⋯ ,d_Kd\_1, \cdots, d\_K를 공백을 사이에 두고 순서에 상관없이 출력한다.

조건을 만족하는 수열이 여러 개라면, 아무 수열이나 하나 출력한다.

조건을 만족하는 수열이 존재하지 않으면 -1만 출력한다.

힌트

gcd⁡(d_1,⋯ ,d_K)\operatorname{gcd}(d\_1, \cdots, d\_K)는 d_1,⋯ ,d_Kd\_1, \cdots, d\_K의 공통된 약수 중 가장 큰 양의 정수를 뜻하고, lcm⁡(d_1,⋯ ,d_K)\operatorname{lcm}(d\_1, \cdots, d\_K)는 공통된 배수 중 가장 작은 양의 정수를 뜻한다.

예제2

  1. 예제 1

    입력
    2 36 3
    
    예상 출력
    4 6 18
    
  2. 예제 2

    입력
    2 8 5
    
    예상 출력
    -1