CF338D.GCD Table

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个大小为 $n \times m$ 的表格 $G$ ，其中 $G(i, j) = \gcd(i, j)$ ，对于所有 $1 \leq i \leq n, 1 \leq j \leq m$ 。 $\gcd(a, b)$ 表示数字 $a$ 和 $b$ 的最大公约数。

你有一个正整数序列 $a_{1}, a_{2}, \ldots, a_{k}$ 。如果这个序列能与表格 $G$ 某一行的连续元素相一致（即从某个位置开始的连续 $k$ 个元素），那么称这个序列在表 $G$ 中出现。更正式地，应该存在 $1 \leq i \leq n$ 和 $1 \leq j \leq m-k+1$ ，使得对于所有 $1 \leq l \leq k$ 都有 $G(i, j+l-1) = a_{l}$ 。

请判断序列 $a$ 是否在表 $G$ 中出现。

输入格式

第一行包含三个用空格分隔的整数 $n$ 、 $m$ 和 $k$ ，满足 $1 \leq n, m \leq 10^{12}$ ， $1 \leq k \leq 10000$ 。

第二行包含 $k$ 个用空格分隔的整数 $a_{1}, a_{2}, \ldots, a_{k}$ ，满足 $1 \leq a_{i} \leq 10^{12}$ 。

输出格式

如果序列 $a$ 出现在表 $G$ 中，输出一行 "YES"（不含引号），否则输出 "NO"（不含引号）。

输入输出样例

输入#1
```
100 100 5
5 2 1 2 1
```
输出#1
```
YES
```
输入#2
```
100 8 5
5 2 1 2 1
```
输出#2
```
NO
```
输入#3
```
100 100 7
1 2 3 4 5 6 7
```
输出#3
```
NO
```

说明/提示

样例 1：表 $G$ 的第十行从 $\{1, 2, 1, 2, 5, 2, 1, 2, 1, 10\}$ 开始。如你所见，从第五个到第九个元素与序列 $a$ 完全一致。

样例 2：这次表 $G$ 的宽度为 8。序列 $a$ 没有在其中出现。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页