cf925Div3D题

Problem - D - Codeforces 

这道题和leetcode的力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

原理是一样的,拿出自己的一部分和另一个数的一部分加和得到目标答案,比如说我们要两个数加和以后可以整除5,显然一个数num1=k1*5+m,这个m是介于0到5之间的数,那我们要找到另一个num2=k2*5+5-m,它两加和后显然等于5的倍数,那么我们可以对每一个数进行预处理,然后找前面有多少个它的另一半即可,题中要求ai+aj整除x,要求ai-aj整除y,那么ai%x的余数要和aj%x的余数相反,ai%y的余数要和aj%y的余数相同,因为是相减嘛,所以顺序是这样的,每次先计算另一半对于ai+aj,ai的另一半是ll u = (x - (a[i] % x)) % x为什么要再模上一个x原因是我们放入cnt时放入的是a[i]%x,它只可能出现0到4,所以查找的时候我们也要把它同化成0,而a[i]%x为0的时候x-0=5,所以要再模上一个5让它变为0.此时cnt[{u, v}]就是当前数可以匹配的另一半的个数.

using ll = long long;void solve() {int n, x, y;std::cin >> n >> x >> y;std::map<std::pair<ll, ll>, ll> cnt;std::vector<ll> a(n);//输入for (int i = 0; i < n; i++) {std::cin >> a[i];}//遍历ll ans = 0;for (int i = 0; i < n; i++) {//a[i]=m1*x+k1,a[i]%x=k1ll u = (x - (a[i] % x)) % x;//a[i]=m2*y+k2,a[i]%y=k2ll v = a[i] % y;//第一个式子(a[i]+a[j])%x==0,对于a[i]%x剩下的加上a[j]%x剩下的加起来等于x//第二个式子模数要相同才能抵消ans += cnt[{u, v}];cnt[{a[i] % x, a[i] % y}] += 1;}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}