B - Make N

https://atcoder.jp/contests/arc139/tasks/arc139_b

三个操作的单价分别为： $\frac{X}{1},\frac{Y}{A},\frac{Z}{B}$ ，如果操作 $1$ 的单价最低肯定直接只用操作 $1$ ，若操作 $1$ 的单价是第二低，那么肯定是先一直用单价最低的，然后最后剩下没处理完的用操作 $1$ 。那么现在主要就是讨论如果操作 $2, 3$ 的单价都比 $1$ 低的情况：

首先我们这里假设操作 $2$ 的单价最低，那么操作 $2$ 可能使用的操作次数上界是 $\lfloor \frac{N}{A} \rfloor$ （再多用一次总值就会超过 $N$ ），操作 $3$ 的操作次数上界是 $A ? 1$ （若大于等于 $A$ ，能整除 $A$ 的部分都可以用操作 $2$ 代替）。那么我们现在考虑枚举上界更小操作，然后分析一下复杂度。

若 $\lfloor \frac{N}{A} \rfloor < A-1$ ，即操作 $2$ 的上界更小，那么我们会发现此时 $A$ 最小也是 $\sqrt N$ 级别的，所以 $\lfloor \frac{N}{A} \rfloor$ 最大也就是 $\sqrt N$ 级别，可以枚举操作 $2$ 的使用次数。

若 $\leq \lfloor \frac{N}{A} \rfloor$ ，即操作 $3$ 的上界更小，那么此时 $A$ 最大也只是 $\sqrt N$ 级别，所以 $A ? 1$ 最大也只是 $\sqrt N$ 级别的，可以枚举操作 $3$ 使用的次数。

所以综上，时间复杂度即为 $O(T\sqrt N)$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// const int N = 2e5 + 10;

// int n, a[N];

ll N, A, B, X, Y, Z;

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int T; scanf("%d", &T);
	while(T--) {
		cin >> N >> A >> B >> X >> Y >> Z;
		if (Y * B > A * Z) {
			swap(A, B); 
			swap(Y, Z);
		}
		if (X * A <= Y) {
			printf("%lld\n", N * X);
		}
		else if (X * B <= Z) {
			printf("%lld\n", N / A * Y + N % A * X);
		}
		else {
			ll ans = 1e18;
			if (N / A < A - 1) {
				for (int i = 0; i <= N / A; ++i) {
					ll n = N - i * A;
					ans = min(ans, i * Y + n / B * Z + n % B * X);
				}
			}
			else {
				for (int i = 0; i <= A - 1; ++i) {
					ll n = N - i * B;
					if (n >= 0) ans = min(ans, i * Z + n / A * Y + n % A * X);
				}
			}
			printf("%lld\n", ans);
		}
	}
}