fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int gcd(int a, int b, int& x, int& y) {
  5. if (b == 0) {
  6. x = 1;
  7. y = 0;
  8. return a;
  9. }
  10. int x1, y1;
  11. int d = gcd(b, a % b, x1, y1);
  12. x = y1;
  13. y = x1 - y1 * (a / b);
  14. return d;
  15. }
  16.  
  17.  
  18. int main(){
  19. int a,b,x,y;
  20. cin>>a>>b;
  21. vector<int>v;
  22. gcd(a,b,x,y);
  23. for(int c=1;c<(a-1)*(b-1);c++){
  24. int x0=x*c,y0=y*c;
  25. bool flag1=1,flag2=1;
  26. // if both flags are 1 that means c can not be represented so we push it to the vector
  27.  
  28. int cnt=x0/b;
  29. x0-=b*cnt,y0+=a*cnt;
  30. if(x0<0) x0+=b,y0-=a;
  31. if(y0>=0) flag1=0;
  32.  
  33. cnt=y0/a;
  34. x0+=b*cnt,y0-=a*cnt;
  35. if(y0<0) x0-=b,y0+=a;
  36. if(x0>=0) flag2=0;
  37.  
  38. if(flag1&&flag2)v.push_back(c);
  39. }
  40. cout<<v.size()<<'\n';
  41. for(auto i:v) cout<<i<<" ";
  42. }
Success #stdin #stdout 0.01s 5288KB
stdin
Standard input is empty
stdout
0