[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】树

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注