General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
86332879 Practice:
JKLover
338D - 10 C++17 (GCC 7-32) Accepted 62 ms 3808 KB 2020-07-09 11:34:50 2020-07-09 11:34:50
→ Source
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(ll x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(ll x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
ll gcd(ll a, ll b)
{
	return __gcd(a, b);
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if (!b)
	{
		x = 1, y = 0;
		return a;
	}
	ll _x, _y, d = exgcd(b, a % b, _x, _y);
	x = _y;
	y = _x - a / b * _y;
	return d;
}
ll mul(ll a, ll b, ll mod)
{
	ll res = a * b - (ll)((long double)a / mod * b + 1e-8) * mod;
	return (res % mod + mod) % mod;
}
const int N = 1e4 + 10;
ll n, m, k, x, y, a[N], r[N];
ll excrt()
{
	ll M = a[1], R = r[1];
	for (int i = 2; i <= k; ++i)
	{
		ll k1, k2, g = exgcd(M, a[i], k1, k2);
		if ((r[i] - R) % g)
			return -1;
		k1 = mul((r[i] - R) / g, k1, a[i]);
		R += k1 * M;
		M = M / g * a[i];
		R %= M;
	}
	return (R - 1 + M) % M + 1;
}
int main()
{
	n = read(), m = read(), k = read();
	a[1] = read(), r[1] = 0, x = a[1];
	for (int i = 2; i <= k; ++i)
	{
		a[i] = read(), r[i] = 1 - i;
		ll g = gcd(x, a[i]);
		x = x / g * a[i];
		if (x > n)
			return puts("NO"), 0;
	}
	y = excrt();
	if (y + k - 1 > m || y < 1)
		return puts("NO"), 0;
	for (int i = 1; i <= k; ++i)
		if (gcd(y + i - 1, x) != a[i])
			return puts("NO"), 0;
	puts("YES");
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details