本文主要是介绍寒假思维训练day22 D. Divisible Pairs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
更新一道赛时想了很久才想通的题。
链接：Problem - 1931D - Codeforces
Part1 题意：
给定一个长度为n的数组a, 再给定两个整数x, y, 其中
, 定义取两个不同索引i, j, 满足
,
的为美丽对，问数组中有几个这样的美丽对。
Part2 题解：
最开始的想法是将两个方程化简得：
，能不能通过扩展欧几里得求出解带入看后面有几个a[j]满足，但实际上，k, b系数的组合是有无数种的，并不是唯一的，所以不能通过扩展欧几里得来得到，那我们考虑余数相消的情况(因为最后%值为0，余数为0)，记录所有数对x的余数r，其的相反数和对y的余数r_，当枚举到时我们先删除，然后找x - r和y - r_，注意r为0的时候要多一种0的组合，具体在代码实现中很清楚。
Part3 代码:
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
using PII = pair<int, int>;
const int N = 1e6 + 10, inf=0x3f3f3f3f;
int n, x, y;
int a[N];
void solve() {cin >> n >> x >> y; map<PII, int> mp; for(int i = 1; i <= n; i ++ ) {cin >> a[i]; int t1 = (a[i] % x + x) % x, t2 = (-a[i] % y + y) % y;mp[{t1, t2}] ++;}int ans = 0; for(int i = 1; i <= n; i ++ ) {int t1 = (a[i] % x + x) % x, t2 = (-a[i] % y + y) % y;mp[{t1, t2}] --; t2 = (a[i] % y + y) % y; int u1[5], u2[5], c1 = 0, c2 = 0; u1[++ c1] = x - t1, u2[++ c2] = y - t2; if(!t1) u1[++ c1] = 0;if(!t2) u2[++ c2] = 0; for(int j = 1; j <= c1; j ++ ) for(int k = 1; k <= c2; k ++ ) ans += mp[{u1[j], u2[k]}]; }cout << ans << endl;
}
signed main() {int ts; cin >> ts; while(ts--) {solve(); }return 0;
}这篇关于寒假思维训练day22 D. Divisible Pairs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
