I recently learned such a thing as "Find the number of pairs in two arrays such that their sum is equal to X" and this is all for O (n + m).

But I got a slightly different problem, but I could not solve it by this method. Briefly about the condition:

Given two arrays A and B and the number N. It is necessary to find the number of numbers p (from 1 to N) such that (p div Ai) == (p mod Bj).

Limitations:

N, Ai, Bi <= 10 ^ 5

n, m <= 200

Example:

7 2 2 3 4 2 3

Conclusion:

five

Explanation:

The numbers [2,3,4,5,7] are suitable for us because there are pairs: (2 div 3 == 2 mod 2), (3 div 3 == 3 mod 2), (4 div 3 == 4 mod 3 ), (5 div 3 == 5 mod 2), (7 div 4 == 7 mod 3).

My attempt:

#include <cstdio> #include <vector> #include <algorithm> using namespace std; int main() { int n, a, b; scanf("%d%d%d", &n, &a, &b); vector <int> arr1(a); for (int i = 0; i < a; i++) { scanf("%d", &arr1[i]); } vector <int> arr2(b); for (int i = 0; i < b; i++) { scanf("%d", &arr2[i]); } sort(arr1.begin(), arr1.end()); sort(arr2.begin(), arr2.end()); int total = 0; for (int p = 1; p <= n; p++) { int i = 0; int j = b - 1; while (i < a && j >= 0) { if (p / arr1[i] == p % arr2[j]) { total++; break; } else if (p / arr1[i] < p % arr2[j]) { j--; } else i++; } } printf("%d", total); return 0; }
  • How can I put it ... the fact that a> b does not mean that p% a and p% b are related by some relation ... For example, 5> 3. 5% 5 <5% 3, but 6 % 5> 6% 3 ... - Harry
  • Here's a problem, and the solution through HashMap goes to TimeLimit - GGO
  • But the first value - p / a - should be less than b, and this can already be used to cut off the extra b. Or a :) - Harry
  • By the way, the problem you mentioned about the sum for O (n + m) is for already sorted arrays? Or have you sorted by counting? - Harry
  • Yes it is already in sorted. - GGO

2 answers 2

The idea is a cycle for all p from 1 to N, then, for each b, we search using binary search for a suitable a; if we find - hurray, nothing else is needed ...

 #include <vector> #include <string> #include <iostream> #include <iomanip> #include <algorithm> using namespace std; int check(int p, const vector<int>& A, const vector<int>& B) { for(auto b: B) { int z = p%b; auto r = lower_bound(A.begin(),A.end(),p/(z+1)); for(;r != A.end(); ++r) { int a = *r; if (p/a == z) return 1; if (a*z > p) break; } } return 0; } int main(int argc, const char * argv[]) { int n,ca,cb; cin >> n >> ca >> cb; vector<int> a(ca),b(cb); for(int i = 0; i < ca; ++i) cin >> a[i]; for(int i = 0; i < cb; ++i) cin >> b[i]; sort(a.begin(),a.end()); sort(b.begin(),b.end()); int count = 0; for(int p = 1; p <= n; ++p) count += check(p,a,b); cout << count << endl; }
  • first question. Why cycle in the check method? You can make lower + upper_bound and the difference between them - pavel
  • @pavel Yes, something I am confused in these divisions completely, well, and stuck. It does not go beyond iteration 1 :) And in lower_ and upper_ I had great suspicions that this might not work. I have little experience with working with them :( - Harry
  • for sure. From the end you need to do this task. We have a balance. We are going through an array with divisors (!) And then multiply the work of technology. The complexity is reduced to O (a * b) and you can not even sort. - pavel
  • @pavel pereproiznesite :) Something did not understand. I had a thought to somehow convert a*(p mod b) , but for me these remnants are a dark forest ... - Harry
  • now make out. The idea is that n div a = n mod b for example, when a=b has a solutions (for each range with the same partial, 1 residue fits). If a != b then it will be similar, we have only b residues. For each range with such private it is easy to calculate the number of residues. ( a/b and plus one if the ending is suitable). It remains to fasten the restriction on N and compress into the formula. - pavel

Thanks to the idea of ​​Harry, adding C ++ chips, wrote a working program that comes in. Here it is, if someone needs:

 #include <bits/stdc++.h> using namespace std; int main() { int n, m, k; scanf("%d %d %d",&k,&n,&m); vector <int> a(n); for (int i = 0;i < n;i++){ scanf("%d",&a[i]); } vector <int> b(m); for (int i = 0;i < m;i++){ scanf("%d", &b[i]); } vector <int> v(m); int pair = 0; for (int p = 1;p <= k;p++){ for (int i = 0;i < m;i++){ v[i] = p % b[i]; } sort(v.begin(),v.end()); for (int i = 0; i < n; ++i) { if (binary_search(v.begin(),v.end(),p / a[i])) { pair++; break; } } } printf("%d\n", pair); return 0; }