UVA 12220 - Divisible Subsequences Solution

 

Problem Link :  https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3372

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. const int mx = 5e4 + 9;
5. using ll = long long;
6. ll pre[mx];
7. int32_t main() {
8. ios_base::sync_with_stdio(0);
9. cin.tie(0);
10. int t;
11. cin >> t;
12. while (t--) {
13. int n, d;
14. cin >> d >> n;
15. int a[n + 1];
16. for (int i = 1; i <= n; i++) {
17. cin >> a[i];
18. }
19. pre[0] = 0;
20. for (int i = 1; i <= n; i++) {
21. pre[i] = a[i] + pre[i - 1];
22. }
23. ll ans = 0;
24. map<int, int> cnt;
25. cnt[pre[0] % d]++;
26. for (int l = 1; l <= n; l++) {
27. ans += cnt[pre[l] % d];
28. cnt[pre[l] % d]++;
29. }
30. cout << ans << "\n";
31. }
32. return 0;
33. }