#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.
@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 - elementary number theory - How to find solutions of linear Diophantine ax + by = c? - Mathematics Stack Exchange