#include <unordered_map>
#include <cstdio>
#include <algorithm>
#include <boost/functional/hash.hpp>
using namespace std;
/*
template <>
struct hash<pair<long long, long long> > {
public:
size_t operator()(pair<long long, long long> x) const throw() {
size_t h = (x.first << 32) | ((x.second << 32) >> 32);
return h;
}
};
*/
unordered_map<pair<long long, long long>, long long, hash<pair<long long, long long>>> dp;
long long a, b, p, q;
const long long INF = 1000000ll * 1000000ll * 500000ll;
long long getAns(long long a, long long b)
{
if(a == 0 || b == 0) return 0;
pair<long long, long long> cur = make_pair(a, b);
if(dp.count(cur)) return dp[cur];
long long ret = p + getAns(b, a % b);
if(a >= b)
{
long long howMany = a / b;
if(howMany <= ret / (double)q)
{
long long cand = howMany * q + getAns(a % b, b);
ret = min(cand, ret);
}
}
else
{
long long howMany = b / a;
if(howMany <= ret / (double)q)
{
long long cand = howMany * q + getAns(a, b % a);
ret = min(cand, ret);
}
}
return dp[cur] = ret;
}
int main(void)
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%lld %lld %lld %lld", &a, &b, &p, &q);
dp.clear();
printf("%lld\n", getAns(a, b));
}
return 0;
}
Compilation message
mcg.cpp:4:37: fatal error: boost/functional/hash.hpp: 그런 파일이나 디렉터리가 없습니다
#include <boost/functional/hash.hpp>
^
compilation terminated.
