[Codeforces710D]Two Arithmetic Progressions（扩展中国剩余定理）

2019-11-06 08:10:43

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

x=a1k+b1,y=a2l+b2 $x=a_1k+b_1,y=a_2l+b_2$ 也就是说 x≡b1(moda1) $x/equiv b_1/pmod {a_1}$ x≡b2(moda2) $x/equiv b_2/pmod {a_2}$ 将两个方程用扩展中国剩余定理合并一下求出x 然后计算一下在[L,R]内的合法解个数就行了还有一个需要注意的是k,l≥0 $k,l/ge 0$ 也就是说x≥max(b1,b,2) $x/ge max(b_1,b,2)$ 所以要将L更新一下

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define LL long longLL m1,m2,c1,c2,L,R,c,m,t,ans;LL gcd(LL a,LL b){ if (!b) return a; else return gcd(b,a%b);}void exgcd(LL a,LL b,LL &x,LL &y){ if (!b) x=1,y=0; else exgcd(b,a%b,y,x),y-=a/b*x;}LL inv(LL a,LL b){ LL x=0,y=0; exgcd(a,b,x,y); x=(x%b+b)%b; if (!x) x+=b; return x;}int main(){ scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&m1,&c1,&m2,&c2,&L,&R); L=max(L,max(c1,c2)); if (L>R) { puts("0"); return 0; } c1%=m1,c2%=m2; t=gcd(m1,m2); if ((c2-c1)%t) { puts("0"); return 0; } m=m1*m2/t; c=(inv(m1/t,m2/t)*((c2-c1)/t))%(m2/t)*m1+c1; c%=m; if (c>R) { ans=(c-R)/m-(c-L)/m; if ((c-R)%m==0) ++ans; } else if (c<L) { ans=(R-c)/m-(L-c)/m; if ((L-c)%m==0) ++ans; } else ans=(R-c)/m+(c-L)/m+1; PRintf("%I64d/n",ans);}

上一篇：计算阶乘和

下一篇：【LeetCode】36. Valid Sudoku