\(Description:\)
给出一个长度为k的数列a，给出n,m，有一个矩阵满足\(gcd(i,j)\)为第i行j列的元素。
问这个矩阵中是否有满足\(gcd(x,y+i-1)=a_i\)的x,y。
\(Sample\) \(Input\) \(1\):
100 100 5
5 2 1 2 1
\(Sample\) \(Output\) \(1\):
YES
\(Sample\) \(Input\) \(2\):
100 8 5
5 2 1 2 1
\(Sample\) \(Output\) \(2\):
NO
\(Solution:\)
听说这是一道把XLH搞自闭的题，震惊(ΩДΩ)！！！。
乍眼看除了暴力毫无思路，好好思考之后发现，好像x是所有\(a_i\)的最小公倍数
那么直接判断x可以得到40分的好成绩，考虑正解
\(y+i-1\)是\(a_i\)的整数倍，那么好像可以用同余式写出来：
\(y+i-1 \equiv 0 \pmod {a_i}\)
\(y\equiv 1-i \pmod {a_i}\)
那么就列出了一堆式子，那么就可以直接用excrt 求解
求出来再吧x,y带回去验证
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,X,Y,k;
namespace subtask2{
const int N=1e5;
int a[N+5],b[N+5],t[N+5];
inline int gcd(int a,int b){
int tmp=0;
while(b!=0){
tmp=a%b;
a=b;
b=tmp;
}
return a;
}
inline int mul(int a,int b,int p){
int ret=0;
while(b>0){
if(b&1) ret=(ret+a)%p;;
a=(a+a)%p;
b>>=1;
}
return ret;
}
inline int Exgcd(int a,int b,int &x,int &y){
if(b==0) { x=1;y=0;return a;}
int tmp=Exgcd(b,a%b,x,y);
int z=x;x=y;y=z-a/b*y;
return tmp;
}
inline int excrt(){
int M=b[1],ans=a[1],x=0,y=0;
for(int i=2;i<=k;++i){
int oo=((a[i]-ans)%b[i]+b[i])%b[i];
int p=Exgcd(M,b[i],x,y);
if(oo%p!=0) return -1;
x=mul(x,oo/p,b[i]/p);
ans+=x*M;
M=M/p*b[i];
ans=(ans%M+M)%M;
}
ans=(ans%M+M)%M;
X=M;
if(!ans) return M;
return ans;
}
void solve2(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=k;++i) scanf("%lld",&t[i]);
for(int i=1;i<=k;++i) b[i]=t[i],a[i]=((1-i)%b[i]+b[i])%b[i];
Y=excrt();
if(Y==-1) { puts("NO");return;}
if(Y+k-1>m || X>n) { puts("NO");return;}
for(int i=1;i<=k;++i)
if(gcd(X,Y+i-1)!=t[i]) { puts("NO");return;}
puts("YES");
}
}
signed main(){
subtask2::solve2();
return 0;
}