纪念第一次赛时想到 G 正解。（虽然没调出来）

【题目大意】

给定 $n,a,b,c,k(n \le 10^6,a,b,c \le 10^9,k \le 10^{15})$，求满足 $1 \le x,y,z \le n,ax + by + cz = k$ 的数对 $(x,y,z)$ 数量。

【题目分析】

裸的 exgcd。由于 $n$ 不大，可以直接枚举 $x$ 的值，再 exgcd 计算方程 $by+cz = k-ax$ 的解数，累加答案即可。时间复杂度 $\mathcal O(n \log n)$。

下文默认你已经会了【模板】exgcd，并将使用类似的推导方法解方程 $ax+by = c$（$\gcd(a,b) = 1$）。注意这里变量名与上面不同。

设 exgcd 跑出来的解为 $x_1,y_1$，则通解可以表示为 $x = x_1 + kb,y = y_1 - ka$，其中 $k$ 为整数。

解不等式组：

$$\begin{cases}1 \le x_1 +kb \le n\\1 \le y_1 -kb \le n\end{cases}$$

得

$$\begin{cases}\lceil \dfrac{-x_1+1}{b}\rceil \le k \le \lfloor \dfrac{n-x_1}{b}\rfloor\\\lceil \dfrac{y_1-n}{a}\rceil \le k \le \lfloor \dfrac{y_1-1}{a}\rfloor\end{cases}$$

请注意下取整和上取整的区别。

那么将两个解集合并即可。

【代码】

代码实现上，要注意几个点：

• 本题卡 long double，上下取整必须使用 __int128。一个常见的 trick 是 $\lceil \dfrac{a}{b}\rceil = \lfloor \dfrac{a+b-1}{b}\rfloor$。

• 注意 C++ 中的除法运算符是向零取整，即 $-8 \div 3$ 的值在 C++ 中计算结果为 $-2$。因此需要特判被除数为负数时的上下取整细节。

• 记得全程开 __int128。推荐直接 define。

#include <bits/stdc++.h>
using namespace std;
#define int __int128
int n,a,b,c,ax,ans;
long long nn,aa,bb,cc,xx;
void exgcd(int a,int b,int &x,int &y){
    if(!b) return x = 1,y = 0,void();
    exgcd(b,a % b,y,x);y = y - (a / b) * x;
}
int gcd(int a,int b){return (b ? gcd(b,a % b) : a);}
int solve(int a,int b,int c){
    int k = gcd(a,b), x,y;
    if(c % k || c <= 0) return 0;
    a /= k,b /= k,c /= k,exgcd(a,b,x,y),x *= c,y *= c;
    int l1 = (-x+1+b-1) / b,l2 = (y - n + a - 1) / a;
    if(-x + b < 0) l1 = (x - 1) / b * -1;
    if(y - n + a - 1 < 0) l2 = (-y + n) / a * -1;
    int r1 = (n - x) / b,r2 = (y - 1) / a;
    if(n - x < 0) r1 = (x - n + b - 1) / b * -1;
    if(y - 1 < 0) r2 = (1 - y + a - 1) / a * -1;
    int l = max(l1,l2),r = min(r1,r2);
    return max(r - l + 1,(int)0);
}
void write( int x ){
	if( x >= 10 ) write( x / 10 );	putchar( x % 10 + 48 );
}
signed main(){
    cin >> nn >> aa >> bb >> cc >> xx;
    n = nn,a = aa,b = bb,c = cc,ax = xx;
    for(int i = 1;i <= n;i ++) ans += solve(b,c,ax - a * i);
    write(ans);
}