# Is my solution for GGCURR correct?

I can’t submit the solution so I am asking here -

``````#include "bits/stdc++.h"
using namespace std;

int main()
{
int t;
cin >> t;

while(t--)
{
int n, a, b;
cin >> n >> a >> b;
int ok[100000+1];
memset(ok, 0, sizeof ok);
queue<int> q;
q.push(0);
while(!q.empty())
{
int x = q.front();
// cout << x;
ok[x] = 1;
q.pop();
if(x+a <= 100000 && ok[x+a] == 0){q.push(x+a);ok[x+a]=1;}
if(x+b <= 100000 && ok[x+b] == 0){q.push(x+b);ok[x+b]=1;}
}
int a1[n+1];
int c = 0;
for(int i = 0; i < n; i++)
{
cin >> a1[i];
if(ok[a1[i]] == 1)
c++;
}
cout << c << " " << n-c << "\n";
}
return 0;
``````

}

There’s one alternative check mine…

``````#include <bits/stdc++.h>
int x, y, d;
void extendedEuclid(int a, int b) {
if (b==0) { x=1; y=0; d=a; return;}
extendedEuclid(b, a%b);
int x1=y;
int y1=x - (a/b)*y;
x=x1;
y=y1;
}

int main() {
int T;
cin >> T;
while (T--) {
int N, A, B;
cin >> N >> A >> B;
int cash=0, digital=0;
extendedEuclid(A,B);
REP(i,1,N) {
int money;
int X, Y;
cin >> money;
if (money%d != 0) {
digital++;
}
else {
X=x, Y=y;
X = X*money/d;
Y=Y*money/d;
int lower = (int)ceil(-(double)X*d/B);
int upper = (int)floor((double)Y*d/A);
if (upper >= lower) {
cash++;
}
else {
digital++;
}
}
}
cout << cash << " " << digital << "\n";

}``````

@terminated your solution is correct as you are precomputing all possible combinations of a and b and then checking for transactions in O(1) and the inner while loop will run for max. 100001 times in the case where one or both of a and b is 1. So, it won’t give TLE.

1 Like