# CodeForces 710D – Two Arithmetic Progressions

0
12

### 洛谷题目页面传送门 & CodeForces题目页面传送门

$$a_1,a_2\in\left(0,2\times10^9\right]\cap\mathbb Z,b_1,b_2,l,r\in\left[-2\times10^9,2\times10^9\right]\cap\mathbb Z,l\leq r$$。

$a_1x+b_1=a_2y+b_2$

$a_1x-a_2y=b_2-b_1$

$a_1(x”+k\Delta x)+b_1\in[l,r]$

$a_1x”+a_1k\Delta x+b_1\in[l,r]$

$a_1k\Delta x\in[l-a_1x”-b_1,r-a_1x”-b_1]$

$k\in\left[\dfrac{l-a_1x”-b_1}{a_1\Delta x},\dfrac{r-a_1x”-b_1}{a_1\Delta x}\right]$

$k\in\left[\max\left(0,\left\lceil\dfrac{l-a_1x”-b_1}{a_1\Delta x}\right\rceil\right),\left\lfloor\dfrac{r-a_1x”-b_1}{a_1\Delta x}\right\rfloor\right]$

int quo_floor(int x,int y){return (x<0)^(y<0)?-(abs(x)+abs(y)-1)/abs(y):x/y;}
int quo_ceil(int x,int y){return (x<0)^(y<0)?-abs(x)/abs(y):(x+y-1)/y;}


#include<bits/stdc++.h>
using namespace std;
#define int long long
int quo_floor(int x,int y){return (x<0)^(y<0)?-(abs(x)+abs(y)-1)/abs(y):x/y;}//下取整
int quo_ceil(int x,int y){return (x<0)^(y<0)?-abs(x)/abs(y):(x+y-1)/y;}//上取整
int exgcd(int a,int b,int &x,int &y){//Exgcd
if(!b)return x=1,y=0,a;
int d=exgcd(b,a%b,y,x);
return y-=a/b*x,d;
}
int a1,a2,b1,b2,l,r;//题目给的参数
signed main(){
cin>>a1>>b1>>a2>>b2>>l>>r;
int x,y,gcd=exgcd(a1,-a2,x,y);
if((b2-b1)%gcd)return puts("0"),0;//无解
x*=(b2-b1)/gcd;y*=(b2-b1)/gcd;//找到特解
int dx=abs(a2/gcd),dy=abs(a1/gcd);
((x%=dx)+=dx)%=dx;y=(a1*x-(b2-b1))/a2;
if(y<0)((y%=dy)+=dy)%=dy,x=(a2*y+(b2-b1))/a1;//找到使x,y都最小的解
int l0=max(0ll,quo_ceil(l-a1*x-b1,a1*dx)),r0=quo_floor(r-a1*x-b1,a1*dx);//k[min],k[max]
cout<<max(0ll,r0-l0+1);//答案
return 0;
}


<

0