Submission #12107

#TimeUsernameProblemLanguageResultExecution timeMemory
12107kriiiMin-cost GCD (GA9_mcg)C++14
57 / 100
1000 ms1212 KiB
#include <stdio.h> #include <algorithm> #include <map> using namespace std; long long a,b,p,q; std::map<pair<long long, long long>, long long> chk; long long go(long long a, long long b) { if (a == 0 || b == 0) return 0; if (a == b) return p < q ? p : q; if (chk.count(make_pair(a,b))) return chk[make_pair(a,b)]; long long &r = chk[make_pair(a,b)]; r = p + go(b,a%b); if (a > b){ long long d = a / b, e = q * d; if (e / d == q) r = min(r, e + go(a-b*d,b)); } else{ long long d = b / a, e = q * d; if (e / d == q) r = min(r, e + go(a,b-a*d)); } return r; } int main() { int T; scanf ("%d",&T); while (T--){ scanf ("%lld %lld %lld %lld",&a,&b,&p,&q); chk.clear(); printf ("%lld\n",go(a,b)); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...