301791: CF338D. GCD Table
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:2
Solved:0
Description
GCD Table
题意翻译
一张$n\times m$ 的表,第$i$ 行第$j$ 列是$GCD(i,j)$ 你有一个长度为$k$ 的数列$a$ ,询问是否存在$i,j$ ,满足对任意的$l$ ,均有$GCD(i,j+l-1)=a_l(1\leq l\leq k)$ 。 Translated by Fheiwn题目描述
Consider a table $ G $ of size $ n×m $ such that $ G(i,j)=GCD(i,j) $ for all $ 1<=i<=n,1<=j<=m $ . $ GCD(a,b) $ is the greatest common divisor of numbers $ a $ and $ b $ . You have a sequence of positive integer numbers $ a_{1},a_{2},...,a_{k} $ . We say that this sequence occurs in table $ G $ if it coincides with consecutive elements in some row, starting from some position. More formally, such numbers $ 1<=i<=n $ and $ 1<=j<=m-k+1 $ should exist that $ G(i,j+l-1)=a_{l} $ for all $ 1<=l<=k $ . Determine if the sequence $ a $ occurs in table $ G $ .输入输出格式
输入格式
The first line contains three space-separated integers $ n $ , $ m $ and $ k $ ( $ 1<=n,m<=10^{12} $ ; $ 1<=k<=10000 $ ). The second line contains $ k $ space-separated integers $ a_{1},a_{2},...,a_{k} $ ( $ 1<=a_{i}<=10^{12} $ ).
输出格式
Print a single word "YES", if the given sequence occurs in table $ G $ , otherwise print "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