原题链接：ABC315G
前置知识：扩展欧几里得算法。如果还不会扩欧的话，建议先去做这道题。
题意
给定 \(n,a,b,c,k\)。求有多少个 \(x,y,z(x,y,z \le n)\) 满足 \(ax+by+cz=k\)。
思路
首先看到题目给出的方程式：\(ax+by+cz=k\)。我们会发现很像扩欧板子中的：\(ax+by=k\)。只不过又多了一个参数 \(c\)。所以我们可以转化一下式子，将原式写为：\(ax+by=k-cz\)。这样我们就可以用 \(O(n)\) 的时间复杂度枚举 \(z\) 的值，然后每一次计算有多少个合法的 \(x,y\) 就行了。
首先用扩欧求出 \(ax+by=\gcd(a,b)\) 这个方程的特解。然后将这个方程的特解乘上 \((k-cz)\div \gcd(a,b)\) 就是方程 \(ax+by=k-cz\) 的特解了。然后我们通过加减增量的方式可以求出此时 \(x\) 的最小合法解和最大合法解。最后就可以计算出答案了。总时间复杂度 \(O(n)\)。
还有几个注意事项：
-
这道题需要开 int128，不然计算过程中可能会炸。
-
如果 \(k-cz\) 不整除 \(\gcd(a,b)\)，那么方程直接无解。
-
\(x,y\) 的范围都是 \(1 \le x,y \le n\)，计算最大最小解的时候要注意。
Code
#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define ll long long
#define inf 0x3f
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
int n,a,b,c,k,x,y,Ga,Gb,ans,nx,ny;
ll N,A,B,C,K,ANS;
inline 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,x,y);
int z = x;x = y,y = z - (a / b) * y;
return d;
}
signed main()
{
scanf("%lld%lld%lld%lld%lld",&N,&A,&B,&C,&K);
n = N,a = A,b = B,c = C,k = K;
int d = Exgcd(a,b,x,y);
Ga = b / d,Gb = a / d;
for(re ll i = 1;i <= n && k > c;i++)
{
k -= c;
if(k % d != 0) continue;
int G = k / d,minx,maxx;
nx = x * G,ny = y * G;
nx = (nx % Ga + Ga - 1) % Ga + 1;
if(ny <= n) ny = n - (n - ny) % Gb;
else ny = ny - ((ny - n - 1) / Gb + 1) * Gb;
minx = max(nx,(k - ny * b) / a);
ny = (ny % Gb + Gb - 1) % Gb + 1;
if(nx <= n) nx = n - (n - nx) % Ga;
else nx = nx - ((nx - n - 1) / Ga + 1) * Ga;
maxx = min(nx,(k - ny * b) / a);
if(maxx >= minx) ans += (maxx - minx) / Ga + 1;
}
ANS = ans;
printf("%lld",ANS);
return 0;
}