### t3rminated's blog

By t3rminated, history, 3 years ago, ,

In this question isn't it enough to check the gcd(A,B) divisibility with each number? i am getting wrong answer!

code--

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//utility function to find the GCD of two numbers
ll gcd(ll a, ll b)
{
return (a%b == 0)? abs(b) : gcd(b,a%b);
}

int main() {
// your code goes here
int t;
cin >> t;
while(t--)
{
ll n, x, y;
cin >> n >> x >> y;
ll gdc = gcd(x,y);
ll a[n+1];
ll c  =0;
for(int i = 0; i < n; i++)
{
cin >> a[i];
if((a[i]%gdc == 0))
c++;

}
cout << c << " " << n-c << "\n";

}
return 0;
}



• -8

 » 3 years ago, # |   0 If we have an equation ax+by = c and if gcd(a,b) divides c, it means the equation will have integral solution however it doesn't state x,y will be positive, We want only positive x,y in this question. For instance 7x+5y = 2 doesn't have a solution where x,y are >= 0 whereas your code will count it as a valid cash payment.
•  » » 3 years ago, # ^ |   0 so what is the proposed solution?
•  » » » 3 years ago, # ^ |   0 We can formulate this question as reachability problem. Initially push 0 in the queue, each time you pop an element from the queue push, (val+a,val+b) in the queue till val+a,val+b are <= 1e5,
•  » » » » 3 years ago, # ^ |   0 but wouldn't the time complexity be too high! like for each element iterating till val+a<=100000
•  » » » » » 3 years ago, # ^ |   +1 NO, we don't iterate for all val+a < 1e5 rather we incrementally see what all values can be reached. Spoilerint ok[100010];queue< int > q;q.push(0);while(!q.empty()) {int x = q.top();ok[x] = 1;if(x+a <= 1e5)q.push(x+a);if(x+b <= 1e5)q.push(x+b);}
•  » » » » » » 3 years ago, # ^ |   0 Yeah this looks good!
•  » » » » » » » 3 years ago, # ^ |   0 So it's complexity will be O(n*t*logn) because for each element we can binary search in the queue whether it's found
•  » » » » » » » » 3 years ago, # ^ |   0 Binary Search? No, We run this as a pre-processing step and then answer in O(1) using 'ok' array.
•  » » » » » » » » » 3 years ago, # ^ |   0 OK yeah thanks!
•  » » » » » » » » » 6 months ago, # ^ |   -8 Or try to find the number of solutions in [0,.....], if the answer is zero, you know what to do :-)
•  » » » » 4 months ago, # ^ |   0 Please Give me little bit info where to study these reachability problems and their theory ThanksI searched and tried to understand but how it is here I wasnt able to get it
 » 4 months ago, # | ← Rev. 2 →   0 the symbol ll is it for container ?
•  » » 4 months ago, # ^ |   +6 New to Cpp? No worries. There's Google. Surely you are not new to Google? Lmao.