#include<stdio.h>
#define M 922337203685477580LL
int t,w;
long long x,y,p,q,dap;
struct data
{
long long x,y;
}a[30];
struct data2
{
long long mi,ma;
}d[30];
void gcd(long long x,long long y)
{
w++; a[w].x=x; a[w].y=y;
if(x%y==0) return;
gcd(y,x%y);
}
int main()
{
int i,j;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
dap=M; w=0;
for(j=1;j<=30;j++) d[j].ma=M, d[j].mi=M;
scanf("%lld %lld %lld %lld",&x,&y,&p,&q);
if(x==y){
if(p>q) printf("%lld\n",q);
else printf("%lld\n",p);
continue;
}
if(x>y) gcd(x,y);
else gcd(y,x);
if(x>y) d[1].ma=0;
else d[1].mi=0;
for(j=2;j<=w;j++)
{
if(d[j].mi>d[j-1].ma+q*(a[j-1].x/a[j-1].y)) d[j].mi=d[j-1].ma+q*(a[j-1].x/a[j-1].y);
if(d[j].ma>d[j-1].ma+p) d[j].ma=d[j-1].ma+p;
if(d[j].ma>d[j-1].mi+q*(a[j-1].x/a[j-1].y)) d[j].ma=d[j-1].mi+q*(a[j-1].x/a[j-1].y);
//if(d[j].ma>d[j].mi+p) d[j].ma=d[j].mi+p;
}
if(dap>d[w].mi+q*(a[w].x/a[w].y)) dap=d[w].mi+q*(a[w].x/a[w].y);
if(dap>d[w].ma+q*(a[w].x/a[w].y)) dap=d[w].ma+q*(a[w].x/a[w].y);
if(dap>d[w].ma+p) dap=d[w].ma+p;
//if(dap>d[w].mi+p+p) dap=d[w].mi+p+p;
printf("%lld\n",dap);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1084 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1084 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
1084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
