题解：CF1373E Sum of Digits

· · 题解

约定

本文约定 \circ 运算符表示将若干个整数依次拼接。
例如 12 \circ 34 \circ 0 = 12340。

显然有 f(a\circ b)=f(a)+f(b)。

方法

因为 k\leq9，所以 x 在进位的时候至多进一位。
再观察样例，就不难想出将答案表示成这样。

x=p \circ \underbrace{99\ldots99}_{t \text{ times}} \circ r

其中，p 是一个末尾不为 9 的数字，r 是一个一位数字。

因为 r 和 t 都非常小，所以我们枚举所有的 r 与 t，然后求出最小的 p。

做法

我们把 x,x+1,x+2,\ldots,x+k-1,x+k 分成两块研究，一块是最后一位进位之前，一块是进位后。
有的时候可能不会进位，也就没有第二块。

第一块大小表示 r 要加多少才能进位，也就是 10-r。
因为总共有 k+1 个数，第一块已经有了 10-r 个，所以第二块就是 (k+1)-(10-r) 个。

要注意的事是：
1.总共有 k+1 个数，所以两块长度都不能超过 k。
2.块长非负。

记两块长度为：

A=\min(k+1,10-r) B=\max(0,(k+1)-(10-r))

那么 x,x+1,x+2,\ldots,x+k-1,x+k 就应该长这样：

\begin{aligned} & \begin{rcases} p \circ 99\ldots99 \circ r \\ p \circ 99\ldots99 \circ (r+1) \\ \vdots \\ p \circ 99\ldots99 \circ 8 \\ p \circ 99\ldots99 \circ 9 \\ \end{rcases} {A} \\ & \begin{rcases} (p+1) \circ 00\ldots00 \circ 0 \\ (p+1) \circ 00\ldots00 \circ 1 \\ \vdots \\ (p+1) \circ 00\ldots00 \circ (B-2) \\ (p+1) \circ 00\ldots00 \circ (B-1) \\ \end{rcases} {B} \end{aligned}

对上面所有数进行 f 函数的操作。
可以得到：

\begin{align*} n &= f(x) + f(x + 1) + \dots + f(x + k) \\ &= Af(p) + 9At + Ar + \frac{A(A-1)}{2} + B\left(f(p)+1\right) + \frac{B(B-1)}{2} \\ &= (k+1)f(p)+B+9At+Ar+\frac{A(A-1)+B(B-1)}{2} \end{align*} \therefore f(p) = \frac{n - B - 9At - Ar - \frac{A(A-1) + B(B-1)}{2}}{k+1}

答案计算

在已知 f(p) 后，为了让 p 尽可能小，就尽可能填入 9，但末尾不能是 9 所以填入 8。

如果 f(p)\leq 8 那么 p=f(p)。
否则填入 8 后尽可能填入 9，形如 p=X \circ99\ldots99 \circ 8。
其中 X 是 f(p) 减掉 8 再模 9 得到的数。

得出这次对应得答案为 p \circ \underbrace{99\ldots99}_{t \text{ times}} \circ r。
所有答案取 \min 即为答案。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF=9e18;

void add(ll &a,ll b){// 拼接函数，将 a 拼上 b
    for(ll b1=b;b1;b1/=10)a*=10;
    a+=b;
}

ll construct(int fp,int t,int r){// 输入 f(p),t,r 返回最小的 x
    ll fr=0;

    if(fp<=8)add(fr,fp);
    else{
        fp-=8;// 末尾会填入 8
        if(fp%9)add(fr,fp%9);
        for(;fp>=9;fp-=9)add(fr,9);// 尽可能用 9
        add(fr,8);// 末尾一个 8，因为 p 的末尾不能是 9
    }

    while(t--)add(fr,9);
    if(r)add(fr,r); else fr*=10;//我的拼接函数拼不上 0
    return fr;
}

ll solve(){
    ll n,k;
    cin>>n>>k;
    ll ans=INF;

    ll A,B;
    for(int t=0;t<=18;t++){
        for(int r=0;r<=9;r++){
            A=10-r; B=(k+1)-(10-r);
            A=min(A,k+1); B=max(B,0LL); //块长限制
            ll D=n-B-9*A*t-A*r-(A*(A-1)+B*(B-1))/2;

            if(D<0 || D%(k+1))continue;
            ll fp=D/(k+1);
            ans=min(ans,construct(fp,t,r));
        }
    }
    if(ans>=INF)return -1;
    return ans;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin>>T;
    while(T--)cout<<solve()<<'\n';
}