CF1931D 题解

yyrwlj · 2024-02-14 13:24:24 · 题解

思路

题目中说要让 a_i + a_j 能被 x 整除，也就是 (a_i + a_j) \operatorname{mod} x = 0。

进一步转换，可以得到 (a_i \operatorname{mod} x + a_j \operatorname{mod} x) \operatorname{mod} x=0。

因为加号两边都肯定小于 x，所以括号里面的和只能是 x 或 0，若是 0，则加号两边的结果都应该为 0。

同理可得 a_i \operatorname{mod} y - a_j \operatorname{mod} y=0，移项得 a_i \operatorname{mod} y=a_j \operatorname{mod} y。

我们可以使用 STL 中的 map<pair<int, int>, int> 来维护。

设当前枚举的 a_j 模 x 和 y 的结果分别是 b 和 c，则往前找的 i 要满足 a_i \operatorname{mod} x=x-b 且 a_i \operatorname{mod} y = c。

要特判如果 b=0，则 a_i \operatorname{mod} x 应该等于 0。

Code

typedef long long LL;
typedef pair<int, int> PII;
void work()
{
    map<PII, int> cnt;
    cnt[{a[1] % x, a[1] % y}] = 1;
    LL ans = 0;
    for (int i=2;i<=n;i++)
    {
        int A = x - a[i] % x;
        if (a[i] % x == 0)
            A = 0;
        ans += cnt[{A, a[i] % y}];
        cnt[{a[i] % x, a[i] % y}] ++;
    }
}