Problem Description
Let's define the sum of all digits in x as g(x). For example, g(123)=1+2+3=6. Give you a function:
f(x)=Ax2g(x)+Bx2+Cxg2(x)+Dxg(x)
Find the minimum value of f(x), where x is an integer and 1≤x≤N.
Input
This problem contains multiple test cases.
The first line of the input contains an integer T(1≤T≤104), representing the number of test cases.
Each of the next T lines contains five integers A,B,C,D,N(0≤|A|≤103,0≤|B|,|C|,|D|≤106,1≤N≤106) indicating a test case.
Output
For each test case output an integer, denoting the answer.
Sample Input
2
1 2 3 4 100
4 3 2 1 100
Sample Output
10
10
比赛的时候被1006和傻逼OJ搞了一波心态就没想出来这个题，赛后发现还是比较简单的...哎...
首先(g(x))肯定没法求导，直接做显然不行。考虑到n的范围最大也就是1e6，六个个位数的和最大就是9 + 9 + 9 + 9 + 9 + 9 = 54，因此g(x)的值域实际上是很小的。这样可以考虑枚举(g(x))的值(a)，此时可以发现原函数变成了一个二次函数（(g(x))可以看做是定值了），定义域是1到n中所有满足(g(x) = a)的(x)，要做的就是在这个定义域下求出原函数的最小值。如果开口朝下，就把两个端点值代入更新答案，如果开口朝上则用三分求出来最小值。至于1到54每个(g(x))值对应的(x)可以在一开始的时候就遍历1到1e6预处理出来，push_back进vector数组里，这样也能保证每个vector的数是有序的，满足三分的条件。代码里要注意几处特判。
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v[100];
int maxx = 0;
void calc(int x) {
int sum = 0;
int xx = x;
while(x) {
int now = x % 10;
sum += now;
x /= 10;
}
maxx = max(maxx, sum);
v[sum].push_back(xx);
}
signed main() {
int t;
cin >> t;
for(int i = 1; i <= 1000000; i++) {
calc(i);
}
while(t--) {
int a, b, c, d, n;
cin >> a >> b >> c >> d >> n;
int A, B;
int ans = 1e18;
for(int i = 1; i <= maxx; i++) {
if(v[i].size()) {
A = a * i + b;
B = c * i * i + d * i;
//Ax^2 + Bx在(v[i][0], min(N, v[i][v[i].size() - 1])) 的最小值
vector<int>::iterator it = upper_bound(v[i].begin(), v[i].end(), n);
if(it == v[i].begin()) continue;
it--;
int pos = it - v[i].begin();
if(pos < 0) continue;
if(A < 0) {
if(v[i][pos] <= n) ans = min(ans, A * v[i][pos] * v[i][pos] + B * v[i][pos]);
if(v[i][0] <= n) ans = min(ans, A * v[i][0] * v[i][0] + B * v[i][0]);
} else if(A == 0) {
if(B >= 0) {
if(v[i][0] <= n) ans = min(ans, A * v[i][0] * v[i][0] + B * v[i][0]);
} else {
if(v[i][pos] <= n) ans = min(ans, A * v[i][pos] * v[i][pos] + B * v[i][pos]);
}
} else {
int l = 0, r = pos, mid, midmid;
if(l == r) {//不特判会wa n = 1的情况
if(v[i][l] <= n) ans = min(ans, A * v[i][l] * v[i][l] + B * v[i][l]);
continue;
}
while(l < r) {
mid = (2 * l + r) / 3;
midmid = (2 * r + l + 2) / 3;
if(A * v[i][mid] * v[i][mid] + B * v[i][mid] < A * v[i][midmid] * v[i][midmid] + B * v[i][midmid]) {
ans = min(ans, A * v[i][mid] * v[i][mid] + B * v[i][mid]);
r = midmid - 1;
} else {
ans = min(ans, A * v[i][midmid] * v[i][midmid] + B * v[i][midmid]);
l = mid + 1;
}
}
}
}
}
cout << ans << endl;
}
return 0;
}