关于exgcd的总结
我们主要讨论的是\(ax+by=c\)
1.exgcd算法
1.1 关于解的存在性
有裴蜀定理知，对于方程\(ax+by=c\)存在解的充分必要条件是：\((a,b)|c\)
tips:裴蜀定理 如果\(a,b\)均为整数，则有整数\(x,y\)使得\(ax+by=\gcd(a,b)\)，这个等式称为裴蜀等式。
1.2exgcd算法介绍
要求\(ax+by=c\)，我们可以用\(exgcd\)求出\(ax+by=\gcd(a,b)\)。令\(d = \gcd(a,b)\)。
当我们求出\(ax+by=d\)之后呢，求出的\(x,y\)乘上\(\dfrac{c}{d}\)就是答案啦。
具体处理方法就是:\(ax+by=(a,b)=(b,a\bmod b) = bx'+(a-b\times\lfloor\dfrac{a}{b}\rfloor)y' = ay'+b(x'-\lfloor\dfrac{a}{b}\rfloor y')\)
然后对比两边得到：\(x = y',y = x'-\lfloor\dfrac{a}{b}\rfloor y'\)然后只要一直递归下去就\(ok\)啦。
注意边界条件：\(b = 0\)时候，\(x = 1,y = 0\)是解。
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x = 1,y = 0;
return a;
}
int d = exgcd(b,a%b,y,x);
y -= (a/b)*x;
return d;
}
1.3解的通式
对于\(ax+by=c\)，假设它的其中一个特解是\(x_0,y_0\)，那么我们可以求出它的通解：
\[\begin{cases} x^*=x_0+\dfrac{b}{(a,b)}t\\ y^*=y_0-\dfrac{a}{(a,b)}t \end{cases} \]正确性也很显然，我们感性的去理解一下，因为要保证原式的值不变，那么\(a,b\)应该变化相同的倍率。
1.4关于\(exgcd\)的解
我们知道，对于\(ax+by=c\)的题解是：
\[\begin{cases} x^*=x_0+\dfrac{b}{(a,b)}t\\ y^*=y_0-\dfrac{a}{(a,b)}t \end{cases} \]\(Q1:\)方程是否有正整数解？
我们发现，
-
当\(a,b\)同号时：\(x^*,y^*\)负相关，即\(x^*\)越大\(y^*\)越小。当求出的\(x\)是最小的时候，有\(y\)是最大的。
-
当\(a,b\)异号时，\(x^*,y^*\)正相关，即同增同减。
所以，一个合理的想法，我们对\(exgcd\)传参时候保证\(a,b\)的非负性。即：若\(a<0,b>0\)，那么传入\(exgcd(-a,b,x,y)\),最后注意讨论变化。
\(Q2:\)那么如何求解最小正整数解？
由通解可知：$x^*=x_0+\dfrac{b}{(a,b)}t $
（*）\(x_{min} = x_0 \bmod \dfrac{b}{(a,b)}\)，相当于保证\(>0\)的情况下减去尽可能多的\(\dfrac{b}{(a,n)}\)。
通过\(x_{min}\)就很容易得到\(y_{max} =\dfrac{c-ax_{min}}{b}\)
\(ax+by=d\)的\(x\)最小的非负整数解\((x,y)\)的板子：
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll xx,yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
int main()
{
int _;cin>>_;
while(_--)
{
ll a, b, x, y, m;
scanf("%lld%lld%lld", &a, &b, &m);
ll d = exgcd(a, b, x, y);
if(m % d != 0)
{
puts("-1");
continue;
}
a /= d;
b /= d;
m /= d;
ll xx = (ll) x * (m % b) % b;
if(xx < 0) xx = xx + b;
ll yy = (ll)(m - a * xx) / b;
if(yy < 0)
puts("-1");
else
printf("%lld %lld\n", xx, yy);
}
}
\(Q3:\)关于正整数解的个数？
根据通式算出上下界即可。
因为是正整数解那么：\(x^* = x_0+\dfrac{b}{(a,b)}t\ge 1\)
于是\(t\ge (1-x_0)\dfrac{(a,b)}{b}\)
又因为是整数，那么取整一下。同理另一边也是一样的道理。
\(\lceil(1-x_0)\dfrac{(a,b)}{b}\rceil \leq t \leq \lfloor(y_0-1)\dfrac{(a,b)}{a}\rceil\)
\(Q4:\)exgcd求出的特解的范围？
对于\(ax+by=\gcd(a,b)\)，当\(a,b\)都不等于\(0\)且\(a\neq b\)的情况下满足绝对值最小。
在数值上有：\(|x|\le \dfrac{|b|}{2},|y|\le \dfrac{|a|}{2}\).
对于\(ax+by=c\)就是\(|x|\le |\dfrac{b}{2c}|,|y|\le |\dfrac{a}{2c}|\)
关于正解和非负解的几个结论：
由于\(ax+by=c\)我们可以转化成\(ax+by=d\)，其中\((d=gcd(a,b))\)的形式去求解,那么下面只说明\((a,b)=1\)的情况：
1.非负整数解
设\(ax+by=c\)，其中\(a,b,c\)均为正整数且\((a,b)=1\)。
- 当\(c>ab-a-b\)时，有非负解，且解的个数为\(N_0 = \lfloor\dfrac{c}{ab}\rfloor\)或\(N_0 = \lfloor\dfrac{c}{ab}\rfloor+1\)
- 当\(c=ab-a-b\)时，没有非负解。
- 当\(c<ab-a-b\)时，恰有\(\dfrac{(a-1)(b-1)}{2}\)个正整数有非负解，具体是哪些不清楚。
2.正整数解
正整数解的个数为：\(N_1 = -\lfloor\dfrac{-c}{ab}\rfloor-1\)或者$ -\lfloor\dfrac{-c}{ab}\rfloor$
- 当\(c>ab\)时有正解
- 当\(c=ab\)时无解
- 当\(c<ab\)时，恰有\(\dfrac{(a-1)(b-1)}{2}\)个正整数有非负解，具体是哪些不清楚。
推论：
- 设\((a,b)=1\)且\(a,b>0\)时，\(ab-a-b\)是不能表示成\(ax+by(x,y\ge 0)\)形式的最大整数。
- 设\((a,b)=1\)且\(a,b>0\)时，\(ab\)是不能表示成\(ax+by(x,y> 0)\)形式的最大整数。
显然如果\(x,y\)可以是负数，那可以表示为任意整数了。
3. \(ax+by=c\)有解的充要条件是方程\(ax+by=c-a-c\)有非负解。
1.5*取模意义下的一元二次方程的最小值
起源是关于这个题中提取的思路。
\(ax+by\)能组成的最小正整数是\((a,b)\)。但是在取模意义下呢？
考虑以下两个问题：
- \((ax+by)\bmod m\)的最小值
- \((ax+by+t)\bmod m\)的最小值
先说结论：
- \((ax+by)\bmod m\)的最小值是：\(\gcd(a,b,m)\)
- \((ax+by+t)\bmod m\)的最小值是\(t \bmod \gcd(a,b,m)\)
\(Pfoof.\)
①先讨论第一个：\((ax+by)\bmod m\)的最小值
\(ax+by=k_1\times \gcd(a,b) = k_1g_1\)
那么我们只要考虑\(k_1g_1 \bmod m\)意义下的最小值即可。
\(k_1g_1 \bmod m\)
设\(k_1g_1 ≡ r (\bmod m)\)，利用同余性质可知\((k_1g_1-r)\)的\(m\)的倍数，于是\(k_1g_1 = k_2m+r\)，移向得\(k_1g_1-k_2m = r\)。
tips：同余 设\(m\)是正整数，若\(a,b\)是整数，且\(m|(a-b)\),则称\(a\)和\(b\)模\(m\)同余。或者说\((a-b)\)除以\(m\)余数为\(0\)。
显然上面这个柿子已经没有模的意义了，那么上面这个\(r\)最小显然是\(\gcd(g_1,m)\)
那么\((ax+by)\bmod m\)的最小值是\(\gcd(g_1,m) = \gcd(a,b,m)\)
②那么对于\(ax+by+t\)呢？
\(ax+by+t = k_1g_1+t = k_2m+r\)
\(r = k_1g_1-k_2m+t = k\times\gcd(g1,m)+t\)
上面这个柿子的含义就是要保证\(t>0\)的前提下减去尽可能多的\(\gcd(g_1,m)\)，那也就是\(r_{min} =t \mod \gcd(a,b,m)\)
有了上面的分析，下面来说这个题就很容易了。
题目是要求：\((sum+ax+by)\bmod m\)的最小值，并求出\(x,y\)。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll n,m;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll xx,yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>m;
ll sum = 0;
for(int i = 1; i <= n; i++)
{
ll x;
cin>>x,sum += x;
}
ll a = n,b = (n+1ll)*n/2,x,y;
//ax+by=k1g1(mod m)
ll g1 = exgcd(a,b,x,y);
//k1g1+tm = k2g2
ll k1,t;
ll g2 = exgcd(g1,m,k1,t);
//ans = min(sum + k2g2)
ll ans = sum%g2;
k1 *= ((ans-sum)/g2)%m;
k1 %= m;
x*=k1,y*=k1;
cout<<ans<<"\n";
cout<<(x%m+m)%m<<" "<<(y%m+m)%m<<"\n";
return 0;
}
1.6 一些习题练习
I. Step
思路：由题意转化得：我们要求出\(\dfrac{k\times(1+k)}{2}\bmod lcm(p_1,p_2...p_n) = 0\)的最小的\(k\)。
设\(lcm(p_1,p_2...p_n) = LCM\)，那么题目转化为\(k\times(1+k)≡0(\bmod 2\times LCM)\)
设\(t = 2\times LCM\)
即：$k\times (1+k)-m\times 2\times t = 0 $
问题转化为求：\(k\times(1+k) = 2\times t \times m\)的最小的\(k\),即求\(2t|k(k+1)\)的最小的\(k\)。不妨假设\(2t = A*B\)，且\(A|k,B|(k+1)\),我们设\(Ax = k,By = k+1\)那么\(Ax +1= By\)，移向得：\(-Ax+By = 1\),这里用\(exgcd\)得到最小的\(x\)。
显然\(A,B\)互质的，我们可以考虑对\(2t\)质因数分解，把不同种的质因数分配到\(A,B\)上(二进制枚举方案)即可，
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll lcm(ll a,ll b)
{
return a/__gcd(a,b)*b;
}
vector<ll>a;
map<ll,ll>mp;
void primer(ll x)
{
for (ll i = 2; i <= x / i; i++)
{
if (x % i == 0)
{
int s = 0;
a.push_back(i);
mp[i] = 1;
while (x % i == 0)
{
x = x / i;
s++;
mp[i]*=i;
}
}
}
if (x > 1)a.push_back(x),mp[x] = x;;
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll xx,yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
ll p[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n;
cin>>n;
for(int i = 1;i <= n; i++)
cin>>p[i];
ll LCM = p[1];
for(int i = 1;i <= n; i++)
LCM = lcm(LCM,p[i]);
ll t = LCM*2;
primer(t);
int sz = a.size();
ll ans = 1e18;
for(int i = 0;i < (1<<sz); i++)
{
ll A = 1,B,x,y;
for(int j = 0;j < sz; j++)
{
if((i>>j)&1)A*=mp[a[j]];
}
B = t/A;
ll d = exgcd(A,B,x,y);
//ax+1=by
//-ax+by = 1
x = -x;
x = (x%(B/d)+(B/d))%(B/d);
if(A*x!=0)
{
ans = min(ans,A*x);
}
}
cout<<ans<<"\n";
return 0;
}
A. Modulo Ruins the Legend
思路：什么讲解exgcd的时候又讲，主要思想就是，先去除取模的意义。什么意思呢？
就是说对于\(ax+by+sum \mod m\)后的最小值即\(min(ax+by+tm+sum)\)的最小值
即\(k2g2+sum\)的最小值。这样我们处理出没有取模意义的等式就可以计算啦。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll n,m,sum;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll xx,yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>m;
for(int i = 1;i <= n; i++)
{
ll x; cin>>x,sum += x;
}
ll a = n,b = (n+1)*n/2,x,y,k1,t;
ll g1 = exgcd(a,b,x,y);
ll g2 = exgcd(g1,m,k1,t);
//ax+by = k1g1 (mod m)
//k1g1+tm = k2g2
//ans = min(sum + k2g2) = sum%g2
//k2 = ((ans-sum)/g2)%m
//k1*=k2
//x*=k1,y*=k1;
ll ans = sum%g2;
cout<<ans<<"\n";
ll k2 = (ans-sum)/g2%m;
k1*=k2,k1%=m;
x *= k1,y*=k1;
cout<<(x%m+m)%m<<" "<<(y%m+m)%m<<"\n";
return 0;
}
M-Water_“范式杯”2023牛客暑期多校训练营1
思路：不妨假设\(x = s_0A+r_0B\)
显然的\(s_0\ge0,r_0\ge0\)时，\(ans = 2*(s_0+r_0)\)
因为不可能同时为负数，那么当\(s_0,r_0\)异号的时候呢？
不妨假设\(s_0>0,r_0<0\)
对于以下的讨论不妨假设\(A>B\)且\(|s_0|>|r_0|\),于是：
\(x = s_0A+r_0B = (s_0+r_0-r_0)A+r_0B = (s_0+r_0)A+(-r_0)(A-B)\)
含义就是喝\(s_0+r_0\)杯\(A\),贡献是\(2*(s_0+r_0)\)，再喝\(-r_0\)杯\(A-B\)水。
对于\(A-B\)需要分\(4\)步考虑：
- 将\(A\)倒满
- 将\(A\)中水导入\(B\),此时杯中：\(A-B,B\)的水
- 将\(A-B\)的水喝掉
- (*)将第二个杯子里面的\(B\)倒掉（如果是最后一步就不要这一步）
那么\(ans2 = 4(-r_0-1)+3\)
最后答案就是\(ans = ans1+ans2 = 2s_0-2r_0-1\)
接下来我们只需先求出一个特解，然后在特解附件去求它的通解就可以了。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll xx,yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
ll A,B,X,x,y;
cin>>A>>B>>X;
ll d = exgcd(A,B,x,y);
if(X%d){
cout<<"-1\n";
continue;
}
else{
//x = xxA+yyB
//x = (xx+yy-yy)A+yyB
//x = (xx+yy)A+(-yy)(A-B)
//ans1 = 2*(xx+yy)
//ans2 = 4*(-yy-1)+3
//ans1+ans2 = 2xx+2yy-4yy-4+3 = 2xx-2yy-1
A /= d;
B /= d;
X /= d;
ll xx = (ll) (x % B) * (X % B) % B;
ll yy = (ll)(X - A * xx) / B;
ll ans = 1e18;
for(int i = -10;i <= 10; i++)
{
ll nx = (xx + B*i),ny = (yy - A*i);
if(nx>=0 && ny>=0)
ans = min(ans,2*(nx+ny));
else ans = min(ans,2*abs(nx-ny)-1);
}
cout<<ans<<"\n";
}
}
return 0;
}
Red-Black Pepper
思路：由于我们只能在一个店买，该商店红辣椒\(a_i\)份一包，黑辣椒\(b_i\)份一包，且只能买整包的。那么要求买到份数恰好是\(n\)，那么就有\(a_ix+b_iy = n\)，含义是在第\(i\)家店买\(x\)包红的和\(y\)包黑的总共\(n\)份。
第\(i\)道菜用了红辣椒可以增加\(a[i]\)的美味值，用黑的增加\(b[i]\)。
我们设\(f(x)\)为买\(x\)份红的可以达到的最大美味值。
我们先考虑一个简单的问题：买\(x\)份红的，\(y\)份黑的的最大美味值是多少？\((x+y=n)\)
让我们感性的去理解一下：假设我全买了黑的，再用贪心的策略把其中\(x\)份换成红的。
全买黑的贡献\(f(0) = \sum_{i = 1}^{n}b[i]\)，对于第\(i\)道菜换成红的\(f(1) = f(0)-b[i]+a[i] = f(0)+(a[i]-b[i])\)
那么我们按照\((a[i]-b[i])\)从大到小排序，贪心的去选那\(x\)个红的。
我们观察\(a[i]-b[i]\)是单减的，可能由某一个(可能是正数)逐渐减小变成负数。
那么我们\(f(x)\)由一个先增后减的趋势，是个有极值的函数(开口向下)。
那么处理好了\(f(x)\)，接下来考虑询问。
很显然\(ax+by=n\)的解用\(exgcd\)可解。
我们先求出来了\(ax+by=\gcd(a,b)\)的一个特解\(x_0,y_0\)
如果说\(n\bmod \gcd(a,b)\ne 0\)，那就无解直接\(continue\)。
否则的话继续讨论。
特解知道了，我们可以进一步求出它们的通解：
\[\begin{cases} x^*=\quad x_0+t\times\dfrac{b}{\gcd(a,b)}\\ y^*=\quad y_0-t\times\dfrac{a}{\gcd(a,b)} \end{cases} \tag{1} \]回归问题\(ax+by=n\)
\[\begin{cases} ax^*=\quad ax_0+a\times t\times\dfrac{b}{\gcd(a,b)} \\ by^*=\quad by_0-b\times t\times\dfrac{a}{\gcd(a,b)} \end{cases} \tag{2} \]\[\begin{cases} ax^*=\quad ax_0+ t\times lcm(a,b) \\ by^*=\quad by_0- t\times lcm(a,b) \end{cases} \tag{3} \]对于\(ax^* = ax_0+t[a,b] = ax_0+td\)
因为\(f(x)\)是有极值的单峰函数，我们可以暴力\(for\)一遍找到最大值和最大值\(maxv\)的横坐标\(high\)
对于通解：\(ax_0+td\)
显然\(t\)最小取\(0\)，最大取\(\dfrac{(n-ax_0)}{d}\)
\(td = \dfrac{(n-ax_0)}{d}*d = (n-ax_0)-(n-ax_0)\% d\)
那么对于通解的最小值就是\(mi =ax_0\)，最大值就是\(mx = ax_0+(n-ax_0)-(n-ax_0) \% d = n-(n-ax_0)\%d\)
然后我们在从任意集中，选择离\(high\)下标最近的两组，取两者的\(\max\)即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
ll n,m,c[N],f[N],a[N],b[N];
bool cmp(int a,int b)
{
return a>b;
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll xx,yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i]>>b[i],c[i] = a[i]-b[i],f[0]+=b[i];
sort(c+1,c+1+n,cmp);
for(int i = 1;i <= n; i++)f[i] = f[i-1]+c[i];
ll high = 0,maxv = f[0];
for(int i = 1;i <= n; i++)
if(f[i]>maxv)high = i,maxv = f[i];
cin>>m;
while(m--)
{
ll a,b,x,y;
cin>>a>>b;
ll g = exgcd(a,b,x,y);
if(n%g){
cout<<"-1\n";
continue;
}
x = x*(n/g)%(b/g);
if(x<0)x+=(b/g);
if(a*x>n){
cout<<"-1\n";
continue;
}
/*
x = x0+b/g*t
y = y0-a/g*t
ax+by = n
ax = ax0+ab/g*t
by = ay0-ab/g*t
ax = ax0+dt
*/
ll d = a/g*b;//lcm
//ax+by = n
//ax+t[a,b] = ax+td
//ax+td = n
//t = (n-ax)/d
//t的最小值显然是0，最大值是(n-ax)/d
ll mi = a*x,mx = n-(n-a*x)%d;
ll ans = max(f[mi],f[mx]);
if(high>=mi && high<=mx)
{
ll l = high-(high-mi)%d;//下取整
ll r = high+(mx-high)%d;//上取整
ans = max(ans,max(f[l],f[r]));
}
cout<<ans<<"\n";
}
return 0;
}
Two Arithmetic Progressions
题意：给定\(a_1,a_2,b_1,b_2,L,R\).要求找出\([L,R]\)中的\(x\)的数量，使得\(x\)满足\(x = a_1k_1+b_1 = a_2k_2+b_2\)。
思路：题目要求\(a_1k_1+b_1 = a_2k_2+b_2\)
我们移向得：\(a_1k_1-a_2k_2 = b_2-b_1\)，写成我们常见写法就是\(a_1x-a_2y = b_2-b_1\)。
显然我们可以用\(exgcd\)直接判无解的情况\((b_2-b_1)\%\gcd(a1,g1)\neq 0\)。那么对于有解的情况呢？
首先因为参数有负数，那么我们可以知道，\(x,y\)是同增同减的。我们可以求得一组最小的\(x,y\)。怎么求呢？
我们可以直接通过\(exgcd\)求得一组特解\(x',y'\)。我们令\(\Delta x= \dfrac{a2}{\gcd(a_1,a_2)},\Delta y = \dfrac{a1}{\gcd(a,b)}\)
那么通解就是：
\[\begin{cases} x=\quad x'+k\times \Delta x\\ y=\quad y'+k\times\Delta y \end{cases} \tag{1} \]又由于\(x,y\)是同增同减的，那么我们要找到一组最小的解，当且仅当：
\(x-\Delta x<0\)或\(y-\Delta y<0\)
我们令\(x'' = x' \% \Delta x,y'' = y'\%\Delta y\)
那么我们的通解就变成了：
\[\begin{cases} x=\quad x''+k\times \Delta x\\ y=\quad y''+k\times\Delta y \end{cases} \tag{2} \]因为我们要求\(a_1k_1+b_1 = a_2k_2+b_2\)有多少属于\([L,R]\)的，那么我们把\(x\)代入\(a_1x+b_1\)得：\(a_1(x''+k\times \Delta x)+b_1\in[L,R]\)
那么可以取的\(k\)的个数就是我们的答案了。
即：\(k\in[\dfrac{L-a_1x''-b_1}{a_1\Delta x},\dfrac{R-a_1x''-b_1}{a_1\Delta x}]\)
接下来我们只需要求出\(k_{min}\)和\(k_{max}\)即可，答案就是\(max(0ll,k_{max}-k_{min}+1)\)
注意：取整要手写，因为当其是负数时候，c++默认往0取整，所以下取整我们要自己写
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll xx,yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
ll floordiv(ll a,ll b)
{
//因为当其是负数时候，c++默认往0取整，所以下取整我们要自己写
if(a%b==0)return a/b;
else if(a>0)return a/b;
else return a/b-1;
}
ll ceildiv(ll a,ll b)
{
if(a%b==0)return a/b;
else if(a>0)return a/b+1;
else return a/b;
}
int main()
{
ll a1,b1,a2,b2,l,r,x,y;
cin>>a1>>b1>>a2>>b2>>l>>r;
ll d = exgcd(a1,a2,x,y);
y = -y;
if((b2-b1)%d){
cout<<"0\n";
return 0;
}
x *= (b2-b1)/d,y *= (b2-b1)/d;
ll dx = abs(a2/d),dy = abs(a1/d);
x = (x%dx+dx)%dx,y = (a1*x-(b2-b1))/a2;
if(y<0)y = (y%dy+dy)%dy,x = (a2*y+(b2-b1))/a1;
ll kmin = max(0ll,ceildiv(l-a1*x-b1,a1*dx));
ll kmax = floordiv(r-a1*x-b1,a1*dx);
cout<<max(0ll,kmax-kmin+1)<<"\n";
return 0;
}