수다닷컴

#includeiostream
#includecstdio
#includevector
#includealgorithm
using namespace std;
int gcd(int a,int b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
#define min(x, y) ((x y) ? x : y)
int main()
{
int a,b,c,x1,x2,x,y,t;
scanf(%d,&t);
while(t--)
{
scanf(%d,&a);
scanf(%d,&b);
scanf(%d,&c);
if(ab)
a^=b^=a^=b;
if(cb)
{
printf(-1\n);
}
else if(c%gcd(a,b)!=0)
{
printf(-1\n);
}
else if(c==b || c==a)
{
printf(\n);
}
else
{
x1=1;
x=0;
y=b;
while(1)
{
if(x==c || y==c)
break;
if(a-xy)
{
x=x+y;
y=0;
}
else
{
y=y-(a-x);
x=a;
}
x1+=1;
if(x==c || y==c)
break;
if(x==a)
{
x=0;
}
else if(y==0)
{
y=b;
}
x1+=1;
}
x2=1;
x=a;
y=0;
while(1)
{
if(x==c || y==c)
break;
if(b-yx)
{
&nbsbsp; y=y+x;
x=0;
}
else
{
x=x-(b-y);
y=b;
}
x2+=1;
if(x==c || y==c)
break;
if(x==0)
{
x=a;
}
else if(y==b)
{
y=0;
}
x2+=1;
}
printf(%d\n,min(x1,x2));
}
}
return 0;
}

신청하기