4.10 T1 &&CF338D GCD Table

发表于 | 阅读次数：

（吐槽）这TM第一题就DIV.1 的D，还给不给活路了啊！！！

【问题描述】

qccxhs很喜欢花，因此qccxhs家有一块很大的$n*m$的花田。
同时花的种类也是多种多样的，第$i$行$j$列的花的种类$s_{i,j}$ 是$i,j$的最大公因数
现在qccxhs邀请你和她一起种花，但是你只记得种花地点满足
你想知道是否有这个$(x,y)$存在

【输入格式】

输入文件名为anaan.in
第一行三个整数$n,m,K$
第二行一个长度为$K$的序列$a$

【输出格式】

输出文件名为anaan.out
若存在，输出”YES”，不然输出”NO” ，不需要输出引号

【输入样例】

100 100 5
5 2 1 2 1

【输出样例】

YES

【数据规模与约定】

本题打包测评
对于100%的数据$K\le 1e4, a_i\le 1e12$

[做题第一灵感]

典型的一看题目就自闭系列题，但是还是头铁硬钢♂

暴力很好想，$O(nmk\log a_i)$枚举$x,y,l$ 每次计算一下。

[分析]

由题意可知

$gcd(x,y+l-1)=a_l$

设$x=na_l,y+l-1=ma_l$

再将$x,y$ 模$a_l$ 得 $x mod a_l =0$ ， $y=(1-l) mod(a_l)$

我们就得到了关于y的同余方程组，用EXCRT解即可

因为x无法解得，我们可以由 所有a的lcm所得

因为lcm与y的gcd是$a_l$ 的倍数，而又是x的约数，那么我们选lcm就是最优的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7; 
#define ll long long 
#define int long long 
void read(int &x)
{
	x=0;
	char ch=getchar();
	int pd=1;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			pd=-pd;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=pd;
}
void write(const int &x)
{
	char ggg[10001];
	int s=0;
	int tmp=x;
	if(tmp==0)
	{
		putchar('0');
		return;
	}
	if(tmp<0)
	{
		tmp=-tmp;
		putchar('-');
	}
	while(tmp>0)
	{
		ggg[s++]=tmp%10+'0';
		tmp/=10;
	}
	while(s>0)
	{
		putchar(ggg[--s]);
	}
}

int gcd(int x,int y)
{
	return !x?y:gcd(y%x,x);
}

ll l,n,m,aa[10010];
ll a[N],b[N];
ll ans,lcm,x,y,bg;
ll mul(ll a,ll b,ll P) 
{
    ll s=0;
    for (;b;b>>=1,a=(a+a)%P) if (b&1) s=(s+a)%P;
    return s;
}
ll exgcd(ll a,ll b,ll &x,ll &y) 
{
    if (!b) {x=1,y=0;return a;}
    ll gd=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return gd;
}
ll excrt() 
{
    ans=a[1],lcm=b[1],x,y;
    for (ll i=2;i<=l;i++) 
	{
        ll B=b[i],A=(a[i]-ans%B+B)%B;
        ll gd=exgcd(lcm,B,x,y),bg=B/gd;
        if (A%gd) return -1;
        x=(x+bg)%bg;
		x=mul(x,A/gd,bg);
        ans+=x*lcm;
        lcm*=bg;
        ans%=lcm;
    }
    return ans==0?lcm:ans;
}

signed main() 
{
    read(n);
    read(m);
    read(l);
    if(l>m)
    {
    	puts("NO");
    	return 0;
	}
    for(register int i=1;i<=l;++i)
    {
    	read(aa[i]);
    	b[i]=aa[i];
	}
	for(register int i=1;i<=l;++i)
	{
		a[i]=(1-i);
		while(a[i]<aa[i])
		{
			a[i]+=aa[i];
		}
		a[i]%=aa[i];
	}
	int yy=excrt();
	if(yy==-1)
	{
		puts("NO");
		return 0;
	 } 
	if(yy+l-1>m)
	{
		puts("NO");
		return 0;
	}
	if(lcm>n)
	{
		puts("NO");
		return 0;
	} 
	for(register int i=1;i<=l;++i)
	{
		if(gcd(lcm,yy+i-1)!=aa[i])
		{
			puts("NO");
			return 0;
		}
	} 
	puts("YES");
}