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;
}
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.
int 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);
}
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.
the symbol ll is it for container ?
New to Cpp? No worries. There's Google. Surely you are not new to Google? Lmao.