Language: C++

#include<bits/stdc++.h>
#define re register
int gcd(re int a,re int b)
{
	if(!b)return a;
	return gcd(b,a%b);
}
void exgcd(re int a,re int b,re int&x,re int &y)
{
	if(!b){x=1;y=0;return;}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
int a,b,c,d,x,y,x1,y1,x2,y2,c1,d1,c2,d2,rd;
long long sol()
{
	re int l=0,r=(y1-y2)/d2-1,xx,yy,xx1,yy1;
	for(re int mid=(l+r+1)/2;l<r;mid=(l+r+1)/2)
	{
		yy=y1-mid*d2,xx=1ll*rd*yy%c;
		if(1ll*x*yy>=1ll*xx*y)l=mid;
		else r=mid-1;
	}
	yy=y1-l*d2;xx=1ll*rd*yy%c;yy1=yy-d2;xx1=1ll*rd*yy1%c;
	re long long xl1=xx-xx1,yl1=yy-yy1,xxl,yyl;
	l=0,r=1e9;
	for(re int mid=(l+r+1)/2;l<r;mid=(l+r+1)/2)
	{
		xxl=x+1ll*mid*xl1,yyl=y+1ll*mid*yl1;
		if((long double)xxl*yy>=(long double)xx*yyl)l=mid;
		else r=mid-1;
	}
	xxl=x+l*xl1,yyl=y+l*yl1;//printf("****%lld %lld %d %d %d %d %d\n",xxl,yyl,xx,yy,xx1,yy1,l);
	re long long ans=std::min(xx?xxl/xx:(1ll<<60),yy?yyl/yy:(1ll<<60));
	xxl+=xl1;yyl+=yl1;
	if(xxl>=0&&yyl>=0)ans=std::max(ans,std::min(xx?xxl/xx:(1ll<<60),yy?yyl/yy:(1ll<<60)));
	return ans;
}
int main()
{
	re int T;
	scanf("%d",&T);
	for(;T--;)
	{
		scanf("%d%d%d%d%d",&a,&x,&b,&y,&c);
		re int g=gcd(a,b);a/=g,b/=g,c/=gcd(c,g);
		g=gcd(a,c);a/=g;c/=g;y/=g;
		g=gcd(b,c);b/=g;c/=g;x/=g;
		exgcd(b,c,x1,y1);
		d=1ll*a*(x1+c)%c;//printf("**%d %d %d c:%d d:%d %lld\n",a,b,gcd(a,b),c,d,1ll*(x1+c)*b%c);
		exgcd(d,c,x1,y1);
		rd=(c-x1)%c;
		c1=c,d1=d;
		while(c1!=0)
		{
			x1=1ll*rd*c1%c;y1=c1;
			c2=c1,d2=d1;
			if(d1)c1%=d1;
			else c1=0;
			if(c1)d1%=c1;
			else d1=0;
			if(d1==0)d1=c1;
			re int x2=1ll*rd*c1%c,y2=c1;
		//printf("****%d %d %d %d %d %d\n",x1,y1,x2,y2,d,d2);
			if(1ll*x*y1>=1ll*x1*y&&1ll*x2*y>=1ll*x*y2)
			{
				printf("%lld\n",sol());break;
			}
		}
	}
}

Compiler output:
a.cc:3:16: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    3 | int gcd(re int a,re int b)
      |                ^
a.cc:3:25: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    3 | int gcd(re int a,re int b)
      |                         ^
a.cc:8:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    8 | void exgcd(re int a,re int b,re int&x,re int &y)
      |                   ^
a.cc:8:28: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    8 | void exgcd(re int a,re int b,re int&x,re int &y)
      |                            ^
a.cc:8:37: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    8 | void exgcd(re int a,re int b,re int&x,re int &y)
      |                                     ^
a.cc:8:47: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    8 | void exgcd(re int a,re int b,re int&x,re int &y)
      |                                               ^
a.cc:14:20: error: 'int y1' redeclared as different kind of entity
   14 | int a,b,c,d,x,y,x1,y1,x2,y2,c1,d1,c2,d2,rd;
      |                    ^~
In file included from /usr/include/features.h:523,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/c++config.h:683,
                 from /usr/include/c++/14/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:33,
                 from a.cc:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:257:1: note: previous declaration 'double y1(double)'
  257 | __MATHCALL (y1,, (_Mdouble_));
      | ^~~~~~~~~~
a.cc: In function 'long long int sol()':
a.cc:17:16: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   17 |         re int l=0,r=(y1-y2)/d2-1,xx,yy,xx1,yy1;
      |                ^
a.cc:17:25: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   17 |         re int l=0,r=(y1-y2)/d2-1,xx,yy,xx1,yy1;
      |                       ~~^~~
a.cc:17:29: error: invalid operands of types 'double (*)(double) noexcept' and 'int' to binary 'operator/'
   17 |         re int l=0,r=(y1-y2)/d2-1,xx,yy,xx1,yy1;
      |                      ~~~~~~~^~~
      |                         |    |
      |                         |    int
      |                         double (*)(double) noexcept
a.cc:17:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   17 |         re int l=0,r=(y1-y2)/d2-1,xx,yy,xx1,yy1;
      |                    ^
a.cc:18:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   18 |         for(re int mid=(l+r+1)/2;l<r;mid=(l+r+1)/2)
      |                    ^~~
a.cc:20:17: error: 'yy' was not declared in this scope; did you mean 'yn'?
   20 |                 yy=y1-mid*d2,xx=1ll*rd*yy%c;
      |                 ^~
      |                 yn
a.cc:20:22: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   20 |                 yy=y1-mid*d2,xx=1ll*rd*yy%c;
      |                    ~~^~~~~~~
a.cc:20:30: error: 'xx' was not declared in this scope; did you mean 'x2'?
   20 |                 yy=y1-mid*d2,xx=1ll*rd*yy%c;
      |                              ^~
      |                              x2
a.cc:24:9: error: 'yy' was not declared in this scope; did you mean 'yn'?
   24 |         yy=y1-l*d2;xx=1ll*rd*yy%c;yy1=yy-d2;xx1=1ll*rd*yy1%c;
      |         ^~
      |         yn
a.cc:24:14: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   24 |         yy=y1-l*d2;xx=1ll*rd*yy%c;yy1=yy-d2;xx1=1ll*rd*yy1%c;
      |            ~~^~~~~
a.cc:24:20: error: 'xx' was not declared in this scope; did you mean 'x2'?
   24 |         yy=y1-l*d2;xx=1ll*rd*yy%c;yy1=yy-d2;xx1=1ll*rd*yy1%c;
      |                    ^~
      |                    x2
a.cc:24:35: error: 'yy1' was not declared in this scope; did you mean 'y1'?
   24 |         yy=y1-l*d2;xx=1ll*rd*yy%c;yy1=yy-d2;xx1=1ll*rd*yy1%c;
      |                                   ^~~
      |                                   y1
a.cc:24:45: error: 'xx1' was not declared in this scope; did you mean 'x1'?
   24 |         yy=y1-l*d2;xx=1ll*rd*yy%c;yy1=yy-d2;xx1=1ll*rd*yy1%c;
      |                                             ^~~
      |                                             x1
a.cc:25:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   25 |         re long long xl1=xx-xx1,yl1=yy-yy1,xxl,yyl;
      |                      ^~~
a.cc:27:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   27 |         for(re int mid=(l+r+1)/2;l<r;mid=(l+r+1)/2)
      |                    ^~~
a.cc:29:17: error: 'xxl' was not declared in this scope
   29 |                 xxl=x+1ll*mid*xl1,yyl=y+1ll*mid*yl1;
      |                 ^~~
a.cc:29:35: error: 'yyl' was not declared in this scope; did you mean 'ynl'?
   29 |                 xxl=x+1ll*mid*xl1,yyl=y+1ll*mid*yl1;
      |                                   ^~~
      |                                   ynl
a.cc:29:49: error: 'yl1' was not declared in this scope; did you mean 'xl1'?
   29 |                 xxl=x+1ll*mid*xl1,yyl=y+1ll*mid*yl1;
      |                                                 ^~~
      |                                                 xl1
a.cc:33:9: error: 'xxl' was not declared in this scope
   33 |         xxl=x+l*xl1,yyl=y+l*yl1;//printf("****%lld %lld %d %d %d %d %d\n",xxl,yyl,xx,yy,xx1,yy1,l);
      |         ^~~
a.cc:33:21: error: 'yyl' was not declared in this scope; did you mean 'ynl'?
   33 |         xxl=x+l*xl1,yyl=y+l*yl1;//printf("****%lld %lld %d %d %d %d %d\n",xxl,yyl,xx,yy,xx1,yy1,l);
      |                     ^~~
      |                     ynl
a.cc:33:29: error: 'yl1' was not declared in this scope; did you mean 'xl1'?
   33 |         xxl=x+l*xl1,yyl=y+l*yl1;//printf("****%lld %lld %d %d %d %d %d\n",xxl,yyl,xx,yy,xx1,yy1,l);
      |                             ^~~
      |                             xl1
a.cc:34:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   34 |         re long long ans=std::min(xx?xxl/xx:(1ll<<60),yy?yyl/yy:(1ll<<60));
      |                      ^~~
a.cc: In function 'int main()':
a.cc:41:16: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   41 |         re int T;
      |                ^
a.cc:46:24: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   46 |                 re int g=gcd(a,b);a/=g,b/=g,c/=gcd(c,g);
      |                        ^
a.cc:49:30: error: invalid conversion from 'double (*)(double) noexcept' to 'int' [-fpermissive]
   49 |                 exgcd(b,c,x1,y1);
      |                              ^~
      |                              |
      |                              double (*)(double) noexcept
a.cc:8:47: note:   initializing argument 4 of 'void exgcd(int, int, int&, int&)'
    8 | void exgcd(re int a,re int b,re int&x,re int &y)
      |                                               ^
a.cc:49:30: error: cannot bind rvalue '(int)y1' to 'int&'
   49 |                 exgcd(b,c,x1,y1);
      |                              ^~
a.cc:51:30: error: invalid conversion from 'double (*)(double) noexcept' to 'int' [-fpermissive]
   51 |                 exgcd(d,c,x1,y1);
      |                              ^~
      |                              |
      |                              double (*)(double) noexcept
a.cc:8:47: note:   initializing argument 4 of 'void exgcd(int, int, int&, int&)'
    8 | void exgcd(re int a,re int b,re int&x,re int &y)
      |                                               ^
a.cc:51:30: error: cannot bind rvalue '(int)y1' to 'int&'
   51 |                 exgcd(d,c,x1,y1);
      |                              ^~
a.cc:56:42: error: assignment of function 'double y1(double)'
   56 |                         x1=1ll*rd*c1%c;y1=c1;
      |                                        ~~^~~
a.cc:63:32: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   63 |                         re int x2=1ll*rd*c1%c,y2=c1;
      |                                ^~
a.cc:63:47: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   63 |                         re int x2=1ll*rd*c1%c,y2=c1;
      |                                               ^~
a.cc:65:33: error: invalid operands of types 'long long int' and 'double(double) noexcept' to binary 'operator*'
   65 |                         if(1ll*x*y1>=1ll*x1*y&&1ll*x2*y>=1ll*x*y2)
      |                            ~~~~~^~~
      |                               |  |
      |                               |  double(double) noexcept
      |                               long long int