模拟赛做到的，结果两个小时都没想出来。

题目要求一个人在等差数列中选一些数，另一个人选剩下的，求他们选的数差的不同个数。

那么设一个人选的和为 \(w\), 总和是 \(sum\), 两个人的差就是 \(2w-sum\), 因为 \(sum\) 不变，所以只要求出 \(w\) 的不同个数就可以了。

设一个人选的数的下标集合是 \(T\), 那么 \(w = x|T| + \sum_{i \in T} (i-1)d\)，将 \(d\) 提出，再设 \(k = |T|, v = \sum_{i \in T} (i-1)\), 式子变成了 \(w = kx + vd\)。再想想 \(v\) 的取值范围，因为 \(i-1\) 是在 \([0, n-1]\) 之间连续的，所以我们非常好确定 \(v\) 的范围，就是 \([\sum_{i=0}^{k-1}i,\ i\cdot n - \sum_{i=1}^ki]\)。

考场上想到也许可以容斥，先把这所有的区间内的个数都加起来，然后找到类似 \(k_1 d = k_2 x\) 的式子去把重复的给减掉，但是这样细节繁多，而且时间上也过不去。

然后就是本题的关键想法：\(kx + vd\) 在模 \(d\) 意义下肯定是相同的。这意味着可以按 \(kx\) 分类，不同类中的肯定是不同的，所以只要处理 \(kx\) 模 \(d\) 相同的行的数就可以了。
我们可以把所有 \(kx\) 模 \(d\) 相同的数转换成数轴的一段。因为同一行的数都间隔 \(d\), 那么同一行就可以直接用 \(v\) 的值来表示，至于处理不同行，只需要将 \(v\) 的左右端点都加上 \(\frac{kx}{d}\) 就可以了。

然后就变成了简单的线段求并。

代码。

#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#define int long long
int n, x, d, ans;
typedef std::vector<std::pair<int, int> > twt;
std::map<int, twt> map;
signed main() {
	scanf("%lld%lld%lld", &n, &x, &d);
	if(x == 0 && d == 0) return puts("1"), 0;
	if(x != 0 && d == 0) return printf("%lld\n", n+1), 0;
	if(d < 0) x = -x, d = -d;
	for(int i = 0; i <= n; i++) {
		int t = i*x, L = (i-1)*i/2+t/d, R = i*n-(i+1)*i/2+t/d;
		t %= d;
		if(t < 0) t += d;
		map[t].push_back(std::make_pair(L, R));
	}
	for(std::map<int, twt>::iterator it = map.begin(); it != map.end(); it++) {
		twt tmp = (*it).second;
		if(!tmp.size()) continue;
		std::sort(tmp.begin(), tmp.end());
		int l = tmp[0].first, r = tmp[0].second;
		for(int j = 1; j < (signed)tmp.size(); j++) 
			if(tmp[j].first > r) ans += r-l+1, l = tmp[j].first, r = tmp[j].second;
			else r = std::max(r, tmp[j].second);
		ans += r-l+1;
	}
	printf("%lld", ans);
}