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

Can you please explain your approach?

@bansal1232 he used extended euclidian algo , because the question is somewhat like find positive integer solutions of Ax + By = a[i] , this is a diophantine equation and it only has “integer” solutions if gcd(A,B) divides a[i] , now if it does divide u need to check for one of its solutions to generalize all solutions like whether they are positive or negative. this will help - http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c

//