Submission #12131

#TimeUsernameProblemLanguageResultExecution timeMemory
12131gs14004Min-cost GCD (GA9_mcg)C++98
100 / 100
978 ms1196 KiB
#include <cstdio> #include <cmath> #include <algorithm> #include <cstring> using namespace std; typedef long long lint; lint dp[100]; lint a,b,p,q; bool calc_valid(lint x, lint y){ double t = log10(x)+log10(y); return t < 18; } lint f(lint x, lint y, int step){ if(x == 0 || y == 0) return 0; if(x >= y){ if(dp[step]) return dp[step]; if(!calc_valid(q,x/y)) return dp[step] = f(y,x%y,step+1) + p; else return dp[step] = min(f(y,x%y,step+1) + p,f(x%y,y,step+1) + q*(x/y)); } else{ if(!calc_valid(q,y/x)) return 5e18; else return f(x,y%x,step+1) + q * (y/x); } } void solve(){ memset(dp,0,sizeof(dp)); scanf("%lld %lld %lld %lld",&a,&b,&p,&q); if(a < b) printf("%lld\n",min(p + f(b,a,0),f(a,b,0))); else printf("%lld\n",f(a,b,0)); } int main(){ int t; scanf("%d",&t); while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...