Python3 解法, 执行用时: 1423ms, 内存消耗: 5724K, 提交时间: 2023-05-03 23:36:00

from math import *

def exgcd(a, b):
    if not b:
        return 1, 0, a

    y, x, g = exgcd(b, a % b)
    y = y - a // b * x
    return x, y, g

def excrt(n, r, p):
    now_p = p[0]
    now_r = r[0]

    for i in range(1, n):
        x, y, g = exgcd(now_p, p[i])
        if (r[i] - now_r) % g != 0:
            return -1
        now_r = x * (r[i] - now_r) // g * now_p + now_r
        now_p = lcm(now_p, p[i])
        now_r = now_r % now_p

    if (now_r == 0):
        now_r += now_p
    return now_r;


n, m, k = map(int, input().split(" "))
r = []
p = []

a = list(map(int, input().split(" ")))
    
numa = 1
for i in range(0, k):
    numa = lcm(numa, a[i])
    p.append(a[i])
    r.append((-(i)) % p[i])

ans = excrt(k, r, p)
flag = True
if ans == -1:
    flag = False

for i in range(0, k):
    if gcd(numa, ans + i) != a[i]:
        flag = False
    
if flag and numa <= n and ans + k - 1 <= m:
    print("YES")
else :
    print("NO")

C++ 解法, 执行用时: 11ms, 内存消耗: 564K, 提交时间: 2022-05-20 14:45:09

#include<bits/stdc++.h>
using namespace std;
long long x,y;
long long exgcd(long long a,long long b){
	if(b==0){
		x=1;y=0;
		return a;
	}
	long long d=exgcd(b,a%b);
	long long t=x;
	x=y;
	y=t-(a/b)*y;
	return d;
}
long long a[10005];
long long b[10005];
int main()
{
	long long n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++)
	cin>>a[i];
    for(int i=1;i<=k;i++){
    	b[i]=-i+1;
	}
	a[0]=a[1];
	for(int i=2;i<=k;i++){
		long long temp=exgcd(a[0],a[i]);
		if((b[i]-b[1])/temp==0){
			cout<<"NO";
			return 0;
		}
		long long c=x*(b[i]-b[1])/temp%(a[i]/temp);
		b[1]=a[0]*c+b[1];
		a[0]=a[0]/temp*a[i];
		b[1]=(b[1]%a[0]+a[0])%a[0];
        
        
	}
   
  if(b[1]>m-k+1||a[1]>n) {
cout<<"NO";
      return 0;
  }
 for(int i=0;i<k;i++){    
 	if(exgcd(a[0],b[1]+i)!=a[i+1]){
 		cout<<"NO";
 		return 0;
	 }
 }
 cout<<"YES";
	return 0;
}

pypy3 解法, 执行用时: 175ms, 内存消耗: 34860K, 提交时间: 2022-11-29 23:14:36

from functools import reduce
def gcd(a,b):
    while a:
        a,b=b%a,a
    return b
def lcm(a,b):
    return a//gcd(a,b)*b
def exgcd(a,b):
	if b==0:return 1,0
	x,y=exgcd(b,a%b)
	return y,x-a//b*y
n,m,k=map(int,input().split())
def excrt(s):
	A,B=1,0
	for a,b in s:
		g=gcd(a,A);
		l,k=a*A//g,exgcd(a//g,A//g)[0]
		A,B=l,(b+(B-b)//g*k*a)%l
		if A>n:
			print('NO')
			quit()
	return A,(B+A)%A
a=list(map(int,input().split()))
i,j=excrt([(a[i],-i)for i in range(k)])
if not j:j+=i
if j+k-1>m:
	print('NO')
	quit()
for x in range(k):
	if gcd(i,j+x)!=a[x]:
		print('NO')
		quit()
print('YES')