CF338D GCD Table
个人评价：还好
算法
扩展CRT
题面
给了一张\(n\times m\)的矩阵，第i行j列的权值是gcd(i,j),现在有一个长度为k的序列A，问是否存在(i,j)使得\(gcd(i,j+l-1)=a_l(1\leq l\leq k)\)
问题分析
我们将对应行设为x,对应列设为y，那么就有如下同余方程组
\(x\equiv (y+l-1)(mod\quad a[l])\)
但还是感觉不行，找一下y和a的规律，好像没有办法搞
我们对于x和y分别分析：
1.对于x来说：
序列a中的每一个元素都是x的因数，显然有\(x=lcm(a[i])\times k\),其中\(k\)不一定是一个质数
2.对于y来说：
我们将同余方程拆开,那么可以得到如下方程组
\(y\equiv 0(mod\quad a[1]),y+1\equiv 1(mod\quad a[2])……\)
稍微结合一下下就是
\[\left\{
\begin{aligned}
y\equiv 0(mod\quad a[1]) \\
y\equiv -1(mod\quad a[2]) \\
y\equiv -2(mod\quad a[3]) \\
y\equiv -3(mod\quad a[4]) \\
y\equiv -(k-1)(mod\quad a[k]) \\
\end{aligned}
\right.
\]
然后我们就可以y给解出来，同理，只要判断一下下x是否有解就行了
代码实现（增加代码注释）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll M=1e4+10;
ll n,m,k,a[M];
struct equations{
ll p,r;
}b[M];
ll qmul(ll x,ll y,ll mod){
return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod;
}
ll gcd(ll x,ll y){
if(!y)return x;
return gcd(y,x%y);
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;
return a;
}
ll r=exgcd(b,a%b,x,y),tmp;
tmp=x;x=y;y=tmp-(a/b)*y;
return r;
}
ll inv(ll a,ll b){
ll x,y;
x=0,y=0;
exgcd(a,b,x,y);
while(x<0)x+=b;
return x;
}
void init(){
for(ll i=1;i<=k;i++){
b[i].p=a[i];
b[i].r=1-i;
b[i].r=(b[i].r+b[i].p)%b[i].p;
}
}
ll solve(){//这个excrt卡了我半年……
int fg=1;
for(ll i=2;i<=k;i++){
ll mul1=b[i-1].p,mul2=b[i].p;
ll r1=b[i-1].r,r2=b[i].r;
ll GCD=gcd(mul1,mul2);
if((r2-r1)%GCD!=0){
printf("NO");
exit(0);
}
b[i].p=(mul1*mul2)/GCD;
b[i].r=qmul(qmul(inv(mul1/GCD,mul2/GCD),(r2-r1)/GCD,mul2/GCD),mul1,b[i].p)+r1;
b[i].r=(b[i].r%b[i].p+b[i].p)%b[i].p;
}
if(fg==0||k==1)return -1;
if(b[k].r==0)return b[k].p;
return b[k].r;
}
int main(){
ll lcm=1;
scanf("%lld%lld%lld",&n,&m,&k);
for(ll i=1;i<=k;i++){
scanf("%lld",&a[i]);
lcm=lcm/gcd(lcm,a[i])*a[i];
if(lcm>n){//注意越界判断
printf("NO");
return 0;
}
}
init();
ll y=solve();
if(y+k-1>m){//同样是越界判断
printf("NO");
return 0;
}
for(int i=1;i<=k;i++){
if(gcd(lcm,y+i-1)!=a[i]){//对于x的分析可得
printf("NO");
return 0;
}
}
printf("YES");
return 0;
}
总结
我们在一些数论的题目当中试着将一些公式带数据yy套进去，看一下能不能套对，反正数论的基础公式就那几个