借此题介绍一种打在线比赛快速过规律题的技巧。本题解没有严谨证明，想看证明请移步其他题解。

首先写出暴力程序：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005];
int main() {
	int t; cin >> t;
	while(t--) {
		int n,k,d; cin >> n >> k >> d;
		a[1] = k;
		for(int i = 2;i <= n;i++) a[i] = a[i-1] + d;
		ll num = 0;
		for(ll i = 1;i <= n;i++) {
			for(ll j = i;j <= n;j++) {
				ll sum = 0;
				for(int k = i;k <= j;k++) sum += a[k];
				if(sum % (j-i+1) == 0) num++;
			}
		}
		cout << num << endl;
	}
	return 0;
}

此时提交可以获得 $28$ 分的高分。

看部分分：此时 $k=1$。

那么我们先将所有的 $k=1,2,3,\dots$ 和 $n=5,d=1$ 输入，容易发现 $k$ 的值和答案没有关系。

那么我们接着将 $n=1,2,3,4,\dots$ 和 $k=1,d=1$ 输入，得到如下式子：

如果你瞪眼能力强，那么应该可以看出答案了。但是，如果没看出来呢？我们可以使用一个在线查询数列的网站 oeis.org，进入后在输入框输入 $1,2,4,6,9,12$，根据查询结果我们可以得到通项为 $ans = \frac{(n+1)^2}{4}$，于是我们就可以拿到这档部分分了。此时能拿到 $63$ 分。

那么让我们将这种结论继续扩展：还是用之前的暴力程序，取 $n=6,k=1,d=1,2,3,4,\dots$ 进行求解。可以发现，令 $q \in \N$，当 $d=2q+1$ 时，答案相同；当 $d=2q$ 时，答案也相同。那么当 $d=2q+1$ 时，显然答案和上面 $d=1$ 时答案相同；于是我们取 $d=2,4,6,\dots$ 求解，这个数列很好瞪出来（看不出来，同理使用 OEIS 即可），通项公式即为 $ans=\frac{n(n+1)}{2}$。那么我们只需判断一下 $d$ 的奇偶性即可。至此，我们在本题获得了 $100$ 分。

时间复杂度 $\Theta(1)$。

#include <bits/stdc++.h>
using namespace std;
int main() {
	int t; cin >> t;
	while(t--) {
		int n,k,d; cin >> n >> k >> d;
		cout << (d % 2 ? 1ll * (n+1) * (n+1) / 4 : 1ll * (n+1) * n / 2) << endl;
	}
	return 0;
}

题目要求：$(a_l + \cdots + a_r) \div (r - l + 1)$ 是整数。

即 $\frac{(a_l + a_r)\cdot(r-l+1)\div 2}{r-l+1}$ 为整数。

即 $\frac{(a_l + a_r)}{2}$ 为整数。

即 $a_l+a_r$ 为偶数。

即 $m+(l-1)\cdot d + m+(r-1)\cdot d$ 为偶数。

即 $2m+(l+r-2)\cdot d$ 为偶数。

即 $2m+(l+r)\cdot d -2d$ 为偶数。

因为 $2m,-2d$ 为偶数，所以也就是 $(l+r)\cdot d$ 为偶数。

• 当 $d$ 为偶数时：所有的区间都可以，答案为 $\frac{n\cdot (n+1)}{2}$。

• 当 $d$ 为奇数时：要求 $l+r$ 为偶数，即 $2\cdot l+r-l$ 为偶数，即 $r-l$ 为偶数，也就是这个区间的长度为奇数。

  • 当 $n$ 为偶数时：答案为 $n+(n-2)+\dots 2 =(\frac{n}{2}+1)\cdot \frac{n}{2}$。
  • 当 $n$ 为奇数时：答案为 $n+(n-2)+\dots 1 =\frac{(n+1)\cdot (\frac{n}{2}+1)}{2}$。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
	int n,k,d;
	cin>>n>>k>>d;
	if(d&1){
		if(n%2==0) 
			cout<<(n/2+1)*(n/2)<<'\n';
		else cout<<(n+1)*(n/2+1)/2<<'\n';
	}else{
		cout<<(n)*(n+1)/2<<endl;
	}
}
signed main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}