Submission #12173

#	Time	Username	Problem	Language	Result	Execution time	Memory
12173		imsifile	Min-cost GCD (GA9_mcg)	C++98	100 / 100	280 ms	1084 KiB

mcg

#include<stdio.h>
#include<algorithm>
using namespace std;

typedef long long lld;

lld a, b, p, q, dy[155][2];

void gcd(lld ix, lld x, lld y){
	if(x<y)swap(x,y);
	if(y==0){
		dy[ix][0]=dy[ix][1]=0;
		return;
	}
	gcd(ix+1, y, x%y);
	if((p+dy[ix+1][0]-dy[ix+1][1])/q >= x/y)dy[ix][0]=q*(x/y)+dy[ix+1][1];
	else dy[ix][0]=p+dy[ix+1][0];
	if((p+dy[ix][0]-dy[ix+1][0])/q >= x/y)dy[ix][1]=q*(x/y)+dy[ix+1][0];
	else dy[ix][1]=p+dy[ix][0];
}

int main(){
	int t;
	for(scanf("%d",&t); t--;){
		scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
		gcd(0,a,b);
		printf("%lld\n", dy[0][a<b]);
	}
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 16 / 16
• Subtask 3: 27 / 27
• Subtask 4: 43 / 43