[Function] T9 D25

[Function]( Problem - 7106 (hdu.edu.cn) ) T9 D25

思路：

g(x)的值最大时54，那么预处理出1e6内所有数的g(x),将所有的x分成54中情况，现在每个情况的f[x]是一个一元二次方程，求最小值用三分查找。

#include <bits/stdc++.h>
#define pb push_back
#define ll  long long
#define fi first
#define se second
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const ll mod=1e9+7;
const int qs=1e5+17;
const ll inf = 1e17;
int T;

vector<ll> v[70];

int solve(int x){
    int cnt=0;
    while(x){
        int p=x%10;
        cnt+=p;
        x/=10;
    }
    return cnt;
}
ll a,b,c,d,n;

ll cal(ll i,ll x){
    ll ans=a*x*x*i+b*x*x+c*x*i*i+d*x*i;
    return ans;
}

ll seamin(int i,ll l,ll r){
    ll ans=inf;
    ll midl,midr;

    while(l<=r){ 
        midl=l+(r-l)/3;
        midr=r-(r-l)/3;
        if(cal(i,v[i][midl])<=cal(i,v[i][midr]))
            ans=v[i][midl],r=midr-1;
        else
            l=midl+1;
    } 
    return ans;
}

int main()
{
    T=read();
    for(int i=1;i<=1e6+100;++i){
        int p=solve(i);
        v[p].pb(i);
    }
    while(T--){
        cin>>a>>b>>c>>d>>n;
        ll ans=inf;
        for(int i=1;i<=64;++i){
            if(v[i].size()==0) continue;
            int fp=upper_bound(v[i].begin(),v[i].end(),n)-v[i].begin()-1;
            ll p=seamin(i,0,fp);
            if(p==inf) continue;
            ll f=cal(i,p);
            ans=min(ans,f);
        }
        cout<<ans<<"
";
    }
    return 0;
}