题目简述
$T$ 组询问，每次询问给定 $a,b,c$，你有一个初值为 $0$ 的 $x$，你现在可以进行两种操作:
$1.$ 将 $x$ 变成 $x+1$，或者将 $x$ 变成 $x - 1$，此操作会产生 $a$ 的代价。
$2.$ 将 $x$ 变成 $2x$，此操作会产生 $b$ 的代价。
对于每个询问，你需要输出将 $x$ 变成 $c$ 的最小代价。询问互相独立。
$T\le 10^4,\ c \le 10^{18},\ 0\le a,b \le 10^9$
思路
可以反过来考虑，将 $c$ 变成 $0$ 的最小代价。
首先最简单的操作方法肯定是每次减一，这样的代价是 $c×a$，我们不妨将它作为初始答案，接着考虑使用除以 2 的操作代替一些减法更新答案。
- 如果现在的 $c$ 含有 3（这里指的是二进制下的，即
(c&3)==3），那么可以加一也可以减一，我们可以先加上，然后右移后决策（除了最后一步，永远不会亏）。 - 否则如果含有 1，那么减去比加上更优。
- 否则除以 2 一定最优，因为不会有多余的 1 需要处理。
可以发现决策事实上只会在 $c$ 每次右移后发生，单次询问复杂度为 $logc$。
其实也可以正着考虑：一次乘法之后只有一次加或减，因为如果连续地加或者减，不如在先加（或减）再乘，可以少一个 $a$。于是设 $f_x$ 表示生成 $x$ 的代价，那么有 $f_{2x}=\min(2ax,f_x+b),\ f_{2x+1}=\min{2ax,f_x+a+b,f_{x+1}+a+b}$。可以发现只有 $⌊\frac{c}{2^k}⌋,\ ⌈\frac{c}{2^k}⌉$ 是有效状态，单次询问复杂度为 $logc$。
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#include<vector>
#include<queue>
#define int long long
using namespace std;
int T;
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
signed main(){
T = Read();
while(T--){
int a = Read(), b = Read(), c = Read();
int f = c*a, cost = 0, plus = 0;
while(c){
f = min(f, (c-plus) * a + cost);
plus = 0;
printf("%lld\n", c);
if((c&3) == 3){
c--;
printf("%lld\n", c);
plus = 1;
cost += a;
}
else if((c&1) == 1){
c--;
cost += a;
}
cost += b;
c >>= 1;
}
printf("%lld\n", f);
}
return 0;
}