Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* the gcd function used here is from geeksforgeeks.com*/
- #include<iostream>
- #include<cstdlib>
- #include<algorithm>
- #include<cmath>
- #include<cstdio>
- using namespace std;
- #define MOD 100007
- // code for extended euclid's algorithm
- int gcd(int a, int b, int *x, int *y)
- {
- if (a == 0)
- {
- *x = 0;
- *y = 1;
- return b;
- }
- int x1, y1;
- int gc = gcd(b%a, a, &x1, &y1);
- *x = y1 - (b/a) * x1;
- *y = x1;
- return gc;
- }
- int main()
- {
- int t,n,a,b,num;
- float c;
- cin>>t;
- while(t--)
- {
- cin>>n>>a>>b;
- int x0,y0;//these are the coefficient of a and b respec
- int g1=gcd(a,b,&x0,&y0);
- int cash=0,digital=0;
- //cerr<<g1<<" "<<x0<<" "<<y0<<endl;
- for(int i=0;i<n;i++)
- {
- scanf("%d",&num);
- //if num is a multiple of a or b then it is possible
- if(num%a==0 || num%b==0)
- {
- cash++; continue;
- }
- if(num % g1==0) //change can be made by cash
- {
- //redue a and b such that gcd(a,b)=1
- int ta=a/g1;
- int tb=b/g1;
- float tc=num/g1;
- //cout<<ta<<" "<<tb<<" "<<tc<<endl;
- //find whether positive solutions are there or not
- if(x0 >0 && y0 >0)cash++;
- else if(x0 <0 && y0 < 0 )
- digital++;
- else
- {
- //find the negetive number
- if(y0 < 0)
- {
- int mul=ceil((-1*y0*tc)/ta);
- if((tc*x0 - mul*tb)<=0)
- digital++;
- else
- cash++;
- }
- else
- {
- int mul=ceil((-1*x0*tc)/tb);
- if((tc*y0 - mul*ta)<=0)
- digital++;
- else
- cash++;
- }
- }
- }
- else
- digital++;
- }
- printf("%d %d\n",cash,digital);
- }
- }
Add Comment
Please, Sign In to add comment