题意：给定 \(n,a,b,c,x\)，求满足 \(1 \le i,j,k \le n\) 且 \(ai+bj+ck=x\) 的三元组 \((i,j,k)\) 的个数。\(1 \le n \le 10^6\)，\(1 \le a,b,c \le 10^9\)，\(1 \le x \le 3 \times 10^{15}\)。
考虑到 \(n\) 只有 \(10^6\) 级别，我们可以枚举 \(i\) 来消掉 \(ai\)，这样就变成了求 \(bj+ck=x-ai\) 的二元组 \((j,k)\) 的个数，这个是容易用扩欧求出的，求出来的 \(j\) 和 \(k\) 要调边界到 \([1,n]\) 内，比较麻烦，把 \(j\) 调到区间的最小，把 \(k\) 调到区间的最大，然后对各自的可变化量取个 \(\min\) 即可。
ps：由于可能会炸所以要开 __int128。
感谢 @YukinoYukinoshita 大佬帮调代码。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
__int128 n,m,i,j,ans,a,b,c,x,l,r;
__int128 gcd(__int128 a,__int128 b){
if(b==0) return a;
return gcd(b,a%b);
}
void exgcd(__int128 a,__int128 b,__int128 c){
if(b==0){
l=c/a,r=0;
return;
}
exgcd(b,a%b,c);
__int128 tmp=l;
l=r,r=tmp-a/b*r;
}
inline __int128 read(){
__int128 x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(__int128 x){
if (x<0) putchar('-'),x=-x;
if (x>9) write(x/10);
putchar(x%10+'0');
}
signed main(){
n=read(),a=read(),b=read(),c=read(),x=read();
for(i=1;i<=n;i++){
__int128 k=x-a*i,d=gcd(b,c);
if(k%d!=0 || k<b+c) continue;
exgcd(b,c,k);
__int128 L=c/d,R=b/d;
if(l>0) {l%=L;if(l==0) l+=L;}
else {__int128 cnt=(-l)/L+1;l+=cnt*L;}
if(l>n) continue;
r=(k-b*l)/c;
if(r<=0) continue;
if(r>n){
if((r-n)%R==0) r=n;
else r=r-((r-n)/R+1)*R;
l=(k-c*r)/b;
if(l>n || r<=0) continue;
}
__int128 p1=0,p2=0;
if(r%R==0) p1=r/R;
else p1=r/R+1;
p2=(n-l)/L+1;
ans+=min(p1,p2);
}
write(ans);
return 0;
}