[ABC315G] Ai + Bj + Ck = X (1 <= i, j, k <= N) 题解

原题链接：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;
}