题解 CF468C 【Hack it!】

来一发另类的构造方法。

对于$f(x)$有一个性质：

由此式子可得另一个推广性质：

我们可以把两边都有的那些f(i)减去，那么我们就可以发现两边剩余的分别是

$1+{10}^k$和$1$

$2+{10}^k$和$2$

......

$x+{10}^k$和$x$

根据第一个性质，左边的每一项的函数值都比右边对应项的函数值大$1$，总共加起来就大了$x$。

你只需要性质二就可以做题了。

1. 首先通过数位dp求出1e0~1e19以内的数字之和，具体方法见P2602.

2. 只要我们当前的这个10的幂次的前缀和的答案加上一个小于当前幂次的数模a能变成0，那么我们就可以构造出一个答案。

3. 注意处理前缀和时要取模，如果你要使用__int128，务必记得开C++11.

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
ll a,b,k,ans;
ll ten[30]={1},f[30];
ll cnt[30];
ll mi[30];
ll solve(ll x)
{
    memset(cnt,0,sizeof cnt);
    ll num[30]={0},sum=0;
    int len=0;
    while(x)
    {
        num[++len]=x%10;
        x=x/10;
    }
    for(int i=len;i>=1;i--)
    {
        for(int j=0;j<=9;j++)
        cnt[j]+=f[i-1]*num[i];
        for(int j=0;j<num[i];j++)
        cnt[j]+=ten[i-1];
        ll num2=0;
        for(int j=i-1;j>=1;j--)
        {
            num2=num2*10+num[j];
        }
        cnt[num[i]]+=num2+1;
        cnt[0]-=ten[i-1];
    }
    for(int i=1;i<=9;i++) sum=(sum+i*cnt[i])%k;
    return sum;
}
int main()
{
    scanf("%llu",&k);
    for(int i=1;i<=19;i++)
    {
        f[i]=f[i-1]*10+ten[i-1];
        ten[i]=10*ten[i-1];
    }
    for(int i=0;i<=19;i++)
        mi[i]=solve(ten[i]);
    for(int i=0;i<=19;i++)
        if(k-mi[i]%k<ten[i])
        {
            a=k-mi[i]%k+1;
            b=a+ten[i]-1;
            break;
        }
    printf("%llu %llu",a,b);
    return 0;
}