GCD 테이블과 연속 부분 수열

시간 제한2초메모리 제한512 MB

요약

n, m, k와 수열 a가 주어질 때, GCD 행렬 G[i][j] = gcd(i, j)의 어떤 행 i가 a를 연속한 열 구간으로 포함하는지 판정한다.

난이도: 어려움10점 중 8점
유형: 정수론, 수학, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

크기가 $n \times m$ 인 행렬 $G$ 가 있다. $G[i][j]$ 에는 $i$ 와 $j$ 의 최대공약수가 들어 있다 ( $1 \le i \le n$ , $1 \le j \le m$ ).

길이가 $k$ 인 수열 $a_1, a_2, \dots, a_k$ 가 주어졌을 때, 이 수열이 $G$ 의 한 행에 연속 부분 수열로 나타나는지 판정하는 프로그램을 작성하시오. 즉 모든 $1 \le l \le k$ 에 대해 $G[i][j+l-1] = a_l$ 을 만족하는 $i$ 와 $j$ 가 존재하는지 구해야 한다. 여기서 $1 \le i \le n$ , $1 \le j \le m-k+1$ 이다.

입력

첫째 줄에 $n$ , $m$ , $k$ 가 주어진다 ( $1 \le n, m \le 10^{12}$ , $1 \le k \le 10000$ ).

둘째 줄에 $a_1, a_2, \dots, a_k$ 가 주어진다 ( $1 \le a_i \le 10^{12}$ ).

출력

주어진 수열이 $G$ 에 연속 부분 수열로 나타나면 YES를, 나타나지 않으면 NO를 출력한다.

힌트

첫 번째 예제에서는 $G[10][5]$ 부터 $G[10][9]$ 까지가 주어진 수열과 일치한다.

예제5

예제 1
입력
```
100 100 5
5 2 1 2 1
```
예상 출력
```
YES
```
예제 2
입력
```
100 8 5
5 2 1 2 1
```
예상 출력
```
NO
```
예제 3
입력
```
100 100 7
1 2 3 4 5 6 7
```
예상 출력
```
NO
```
예제 4
입력
```
100 9 5
5 2 1 2 1
```
예상 출력
```
YES
```
예제 5
입력
```
1 1 1
1
```
예상 출력
```
YES
```