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;
} Comments (13)
 » 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.
•  » » so what is the proposed solution?
•  » » » 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,
•  » » » » but wouldn't the time complexity be too high! like for each element iterating till val+a<=100000
•  » » » » » NO, we don't iterate for all val+a < 1e5 rather we incrementally see what all values can be reached. Spoilerint ok;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);}
•  » » » » » » Yeah this looks good!
•  » » » » » » » 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
•  » » » » » » » » Binary Search? No, We run this as a pre-processing step and then answer in O(1) using 'ok' array.
•  » » » » » » » » » OK yeah thanks!
•  » » » » » » » » » Or try to find the number of solutions in [0,.....], if the answer is zero, you know what to do :-)
•  » » » » 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
 » 5 months ago, # | ← Rev. 2 →   the symbol ll is it for container ?
•  » » New to Cpp? No worries. There's Google. Surely you are not new to Google? Lmao.