这道题暴力很容易想到就是：枚举 \(n\) 的倍数 \(m\)，将每个 \(m\) 的方案数加起来。
具体来说就是，先保证 \(a\) 比 \(b\) 小，然后分情况讨论 \(m\)。当 \(m\) 小于等于 \(a\) 时，很明显 \(x\) 可以取满 \(0\) 到 \(a\) 整个范围，方案数就是 \(m+1\)。当 \(m\) 大于 \(a\) 时，如果此时 \(m\) 大于 \(a\) 与 \(b\) 的和，则 \(x,y\) 一定够不到 \(m\)，直接退出循环；否则方案数就是 \(min(a+b-m+1,a+1)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n,a,b,m,ans;
int main(){
cin>>t;
while(t--){
cin>>n>>a>>b,ans=m=0;
if(a>b)swap(a,b);
while(1){
m+=n;
if(m<=a){
ans+=m+1;
}else{
ll p=m-a;
if(p>b)break;
ans+=min(b-p,a)+1;
}
}
cout<<ans<<'\n';
}
}
考虑分三种情况进行快速计算：
对于 \(m\) 小于等于 \(a\) 的 \(m\) 共有 \(\lfloor\cfrac{a}{n}\rfloor\) 个，每个的方案数是 \(m+1\)。可以直接用等差数列求和计算。
对于 \(m\) 大于 \(a\) 且小于等于 \(b\) 的 \(m\) 共有 \(\lfloor\cfrac{b}{n}\rfloor-\lfloor\cfrac{a}{n}\rfloor\) 个，每个的方案数是 \(a+1\)，直接乘即可。
对于 \(m\) 大于 \(b\) 小于等于 \(a+b\) 的 \(m\) 共有 \(\lfloor\cfrac{a+b}{n}\rfloor-\lfloor\cfrac{b}{n}\rfloor\) 个，每个的方案数是 \(a+b-m+1\)，同样也可以用等差数列求和计算。
最终时间复杂度能达到 \(O(t)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n,a,b,m,ans;
int main(){
cin>>t;
while(t--){
cin>>n>>a>>b;
if(a>b)swap(a,b);
ll r=a/n;
ans=(n+(m=r*n))*r/2+r;//第一种情况
r=b/n-r;
ans+=r*(a+1),m+=r*n;//第二种情况
r=(a+b)/n-(m/n);
ans+=r*(b+a+1)-((m+n)+(a+b)/n*n)*r/2;//第三种情况
cout<<ans<<'\n';
}
}