题解 AT2341 【Increasing Numbers】

Ebola · 2018-09-25 21:42:02 · 题解

【AGC011E】Increasing Numbers

首先，显然所有“上升数”都可以表示成9个111...111的和（包括0个1这种数）

那么如果我们用了k个上升数，就有：N=\sum\limits_{i=1}^{9k}111...111(p_i\;is\;the\;number\;of\;'1')

进一步得：N=\sum\limits_{i=1}^{9k}\frac{10^{p_i}-1}{9}

然后进行一些初等变换，就得到了非常美妙的：9N+9k=\sum\limits_{i=1}^{9k}10^{p_i}

于是我们可以枚举k，每当k加一，左边这个数就加9，然后判断式子能否成立即可。

发现右边这个式子的意义就是十进制下各个数位的数字之和不能超过9k，然后由于左边这个数要是9的倍数，所以十进制下各个数位的数字之和必须要是9的倍数，这样判断起来就非常方便了

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

const int N=501010;
char s[N];

struct Bigint
{
    int a[N],n;
    int& operator [] (const int &x){return a[x];}
    Bigint(){memset(a,0,sizeof(a));n=0;}
    Bigint(char *s){n=strlen(s);for(int i=0;i<n;i++)a[i]=s[n-i-1]-'0';}
    void carry()
    {
        for(int i=0;i<n;i++)
        {
            if(a[i]<=9) continue;
            a[i+1]+=a[i]/10;
            a[i]%=10;
            if(i==n-1) n++;
        }
    }
    Bigint& operator *= (int x){for(int i=0;i<n;i++)a[i]*=x;carry();return *this;}
    int get(){int res=0;for(int i=0;i<n;i++)res+=a[i];return res;}
    void gao(int &sum)
    {
        a[0]+=9;sum+=9;
        for(int i=0;a[i]>9;i++)
        {
            sum-=a[i];sum-=a[i+1];
            a[i+1]+=a[i]/10;a[i]%=10;
            sum+=a[i];sum+=a[i+1];
            if(i==n-1) n++;
        }
    }
} A;

int main()
{
    scanf("%s",s);
    A=s;A*=9;
    int sum=A.get(),k;
    for(k=1;true;k++)
    {
        A.gao(sum);
        if(sum<=9*k&&sum%9==0) break;
    }
    cout<<k<<endl;
    return 0;
}