카드

면접 대비

시간 제한5초메모리 제한128 MB

요약

숫자가 적힌 파란 카드와 빨간 카드가 주어질 때, 두 수가 1보다 큰 공약수를 갖는 파란-빨간 짝의 최대 개수를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 정수론, 동적 계획법, BFS
정답자: 아직 제출이 없습니다

문제

탁자 위에 파란 카드와 빨간 카드가 여러 장 놓여 있다. 각 카드에는 $1$ 보다 큰 정수가 하나씩 적혀 있으며, 같은 수가 여러 카드에 적혀 있을 수도 있다.

파란 카드와 빨간 카드에 적힌 두 수가 $1$ 보다 큰 공약수를 가질 때, 두 카드를 짝지을 수 있다. 하나의 파란 카드와 짝지을 수 있는 빨간 카드가 여러 장일 수 있고, 그 반대도 마찬가지다. 파란 카드와 빨간 카드를 한 장씩 골라 짝지으면 두 카드는 탁자에서 제거된다.

예를 들어 파란 카드 네 장에 각각 $2$ , $6$ , $6$ , $15$ 가, 빨간 카드 세 장에 각각 $2$ , $3$ , $35$ 가 적혀 있다고 하자. 이때 다음과 같이 짝지을 수 있다. 먼저 $2$ 가 적힌 파란 카드와 $2$ 가 적힌 빨간 카드를 짝지어 제거한다. 다음으로 $6$ 이 적힌 두 파란 카드 중 하나와 $3$ 이 적힌 빨간 카드를 짝지어 제거한다. 마지막으로 $15$ 가 적힌 파란 카드와 $35$ 가 적힌 빨간 카드를 짝지어 제거한다. 이렇게 하면 제거한 짝은 세 쌍이다.

짝짓는 순서에 따라 만들 수 있는 짝의 총 수가 달라짐에 유의하라. 만약 처음에 $15$ 가 적힌 파란 카드와 $3$ 이 적힌 빨간 카드를 짝지어 제거하면, 그 뒤로는 한 쌍만 더 제거할 수 있어 총 두 쌍이 된다.

주어진 카드들에서 제거할 수 있는 짝의 최대 개수를 구하여라.

입력

입력은 여러 개의 데이터셋으로 이루어진다. 데이터셋의 개수는 $100$ 개 이하이다. 각 데이터셋의 형식은 다음과 같다.

m n
b1 ... bk ... bm
r1 ... rk ... rn

정수 $m$ 과 $n$ 은 각각 파란 카드와 빨간 카드의 개수이며, $1 \le m \le 500$ , $1 \le n \le 500$ 이다. $b_k$ ( $1 \le k \le m$ )와 $r_k$ ( $1 \le k \le n$ )는 각각 파란 카드와 빨간 카드에 적힌 수로, $2$ 이상 $10^7$ ( $=10000000$ ) 미만의 정수이다. 입력의 정수들은 공백 또는 줄바꿈으로 구분된다. $b_m$ 과 $r_n$ 뒤에는 각각 줄바꿈이 온다. 데이터셋에는 그 외의 문자가 없다.

입력의 끝은 공백으로 구분된 두 개의 $0$ 으로 이루어진 줄로 표시된다.

출력

각 데이터셋에 대해, 만들 수 있는 짝의 최대 개수를 나타내는 정수를 한 줄에 출력한다.

예제3

예제 1

입력

4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 439 118 961
0 0

예상 출력

예제 2
입력
```
1 1
6
3
0 0
```
예상 출력
```
1
```
예제 3
입력
```
1 1
2
3
0 0
```
예상 출력
```
0
```