Submission #12127

#	Time	Username	Problem	Language	Result	Execution time	Memory
12127		kriii	Min-cost GCD (GA9_mcg)	C++14	100 / 100	519 ms	1576 KiB

mcg

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

long long a,b,p,q,l;

vector<pair<long long, long long> > u;

void gcd(long long a, long long b)
{
	if (a == 0 || b == 0);
	else if(a > b) gcd(b,a%b);
	else gcd(a,b%a);
	if (a < b) swap(a,b);

	u.push_back(make_pair(a,b));
	if (a != b) u.push_back(make_pair(b,a));
}

int find(vector<pair<long long, long long> > &e, int i, pair<long long, long long> p)
{
	while (i--) if (e[i] == p) return i;
	return -1;
}

int main()
{
	int T; scanf ("%d",&T); while (T--){
		scanf ("%lld %lld %lld %lld",&a,&b,&p,&q);
		u.clear(); l = 1e18 / q;
		gcd(a,b);
		vector<long long> d(u.size());
		for (int i=0;i<u.size();i++){
			if (u[i].first == 0 || u[i].second == 0) d[i] = 0;
			else if (u[i].first == u[i].second) d[i] = p < q ? p : q;
			else{
				long long na = u[i].first, nb = u[i].second;
				d[i] = p + d[find(u,i,make_pair(nb,na%nb))];
				if (na > nb){
					long long nd = na / nb, ne = q * nd;
					if (nd <= l) d[i] = min(d[i], ne+d[find(u,i,make_pair(na-nb*nd,nb))]);
				}
				else{
					long long nd = nb / na, ne = q * nd;
					if (nd <= l) d[i] = min(d[i], ne+d[find(u,i,make_pair(na,nb-na*nd))]);
				}
			}
		}
		printf ("%lld\n",d[find(u,u.size(),make_pair(a,b))]);
	}

	return 0;
}

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