正经题解 | 2024的倍数

题目分析

根据题目分析，容易想到通过暴力循环得到结果，时间复杂度为 $O(n ^ {2})$ 。

不过根据 $N$ 的范围可以看出 $O(n ^ {2})$ 的不能通过。需要考虑通过桶标的方式进行计数优化。比较容易想到的是记录每个数出现的次数，再根据次数进行计算。但因为 $A_i (1 \leq A_i \leq 10^9)$ 的范围，桶的数量也需要考虑优化。

在题目中，因为要统计的是差值为 2024 的倍数的情况，这里会发现，如果 $A_i$ 与 $A_j$ 差值为 2024 的倍数，并且 $A_j$ 与 $A_k$ 的差值也是 2024 的倍数，那么 $A_i$ 与 $A_k$ 差值也应该为 2024 的倍数，所以在创建桶时，可以将桶的数量控制在 2024 数量级内，对每个原始 $A_i$ 对 2024 取模之后，再放入对应桶，后续出现同样数据的数，则与前面同余的数全部构成满足条件的数对，得到答案。

AC代码

#include <iostream>
using namespace std;

const int mod = 2024;
int n,cnt[mod+10];
long long ans;

int main(){
	cin >> n;
	while(n--){
		int x;
		cin >> x;
		ans += cnt[x %= mod] ++;
	}
	cout << ans;
	return 0;
}

复杂度分析

时间复杂度 $O(n)$。