[Codeforces338D]GCD Table（擴展中國剩余定理）

2019-11-08 03:21:39

字體：大中小

來源：轉載

供稿：網友

題目描述

傳送門題意：一個數表，其中G(i,j)=gcd(i,j)，給出一個序列a1…ak，判斷這個序列是否在數表中出現過

題解

人生第一個快速乘，竟然寫在這道題上了… 其實剛開始胡猜了猜寫了寫，沒想到是對的…

行一定是lcm[a1…ak]，如果大于n判掉設列的第一個為x，然后列一些式子 x = a1 * b1 x+1 = a2 * b2 … x+k-1 = ak * bk 搞成同余的形式就是k個模線性方程組用擴展中國剩余定理求解解出x之后回代檢驗因為每一個都是保證的最小正整數解，所以這個做法是正確的中間的計算過程已經超過了long long，所以加一個快速乘

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 10005#define LL long longLL n,M,k,t,lcm;LL a[N],m[N],c[N];LL gcd(LL a,LL b){ if (!b) return a; return gcd(b,a%b);}void exgcd(LL a,LL b,LL &x,LL &y){ if (!b) x=1LL,y=0LL; else exgcd(b,a%b,y,x),y-=a/b*x;}LL inv(LL A,LL Mod){ LL a=A,b=Mod,x=0LL,y=0LL; exgcd(a,b,x,y); x=(x%b+b)%b; if (!x) x+=b; return x;}LL mul(LL a,LL p,LL Mod){ LL ans=0LL,f; if (p<0) a=-a,p=-p; for (;p;p>>=1LL,a=(a+a)%Mod) if (p&1LL) ans=(ans+a)%Mod; return ans;}int main(){ scanf("%I64d%I64d%I64d",&n,&M,&k); for (int i=1;i<=k;++i) scanf("%I64d",&a[i]); lcm=a[1]; for (int i=2;i<=k;++i) { t=gcd(lcm,a[i]); lcm=lcm/t*a[i]; if (lcm>n) {puts("NO");return 0;} } for (int i=1;i<=k;++i) m[i]=a[i],c[i]=a[i]-(LL)i+1LL; for (int i=2;i<=k;++i) { LL m1=m[i-1],c1=c[i-1],m2=m[i],c2=c[i]; t=gcd(m1,m2); if ((c2-c1)%t) {puts("NO");return 0;} m[i]=m1/t*m2; c[i]=inv(m1/t,m2/t); c[i]=mul(c[i],(c2-c1)/t,m2/t); c[i]=mul(c[i],m1,m[i]); c[i]=(c[i]+c1)%m[i]; c[i]=(c[i]%m[i]+m[i])%m[i]; } if (!c[k]) c[k]+=m[k]; if (c[k]>M-k+1LL) {puts("NO");return 0;} for (int i=1;i<=k;++i) { t=gcd(lcm,c[k]+(LL)i-1LL); if (t!=a[i]) {puts("NO");return 0;} } puts("YES"); return 0;}

上一篇：【數據結構6】圖

下一篇：【數據結構5】樹