7097 : 두 수의 GCD 배열
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
N개의 정수로 이루어진 배열이 주어집니다.
배열에서 서로 다른 두 원소를 고르는 모든 쌍 (i, j) (단, i < j)에 대해 두 수의 최대공약수(GCD)를 구합니다.
구해진 모든 GCD 값들의 발생 빈도를 조사하여, GCD 값이 작은 것부터 오름차순으로
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 500$
• 각 원소: $1 \le a_i \le 1{,}000{,}000$
배열에서 서로 다른 두 원소를 고르는 모든 쌍 (i, j) (단, i < j)에 대해 두 수의 최대공약수(GCD)를 구합니다.
구해진 모든 GCD 값들의 발생 빈도를 조사하여, GCD 값이 작은 것부터 오름차순으로
[GCD] [빈도] 형식으로 출력하십시오.[제약 조건]
• 배열 크기 $N$: $1 \le N \le 500$
• 각 원소: $1 \le a_i \le 1{,}000{,}000$
입력 설명
첫째 줄에 배열의 크기 N이 주어집니다. (1 ≤ N ≤ 500)
둘째 줄에 N개의 정수가 공백으로 구분되어 주어집니다. 각 정수는 1 이상 1,000,000 이하입니다.
둘째 줄에 N개의 정수가 공백으로 구분되어 주어집니다. 각 정수는 1 이상 1,000,000 이하입니다.
출력 설명
발생한 모든 GCD 값을 오름차순으로 정렬하여, 각 줄에
GCD값 빈도를 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
2 4 6 8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2 5
4 1도움
이중 루프로 모든 쌍의 GCD를 누적해 정렬 후 출력하십시오.