[AGC011E] Increasing Numbers [数学]

题面

传送门

思路

首先，我们观察一下上升数的性质

可以发现，它一定可以表示为最多9个全是1的数字的和

那么我们设$N$可以被表示成$k$个上升数的和，同时我们设$p_i=\underbrace{111\cdots 11}_{i}$

我们令$a_{i,j}$表示构成$N$的第$I$个上升数的第$j$个全1数的位数

那么可以写出这样的式子

$N=\sum_{i=1}9 p_{a[i][j]}$

我们发现，$p_{i,j}$这样子摆在这里非常不好操作，那么我们继续观察$p_i$的性质，发现：

$p_i=\frac{10^i - 1}{9}$

所以上式可以写成：

$N=\sum_{i=1}9 \frac{10^{a[i][j]}-1}{9}$

我们把9乘过去，再把右边的$9k$个1加过去，得到：

$9N+9k=\sum_{i=1}910^{a[i][j]}$

我们发现：右边这个东西，如果在所有的10的幂加起来的过程中，能够不进位的话，那么它的数位和一定是9k

如果它发生了进位，因为1次进位一定是-10+1，总数位和-9，而9k是9的倍数，所以这个东西的数位和一定是一个小于9k的9的倍数

再看左边，我们发现，实际上我们需要满足的就是$9N+9k$的数位和小于9k且是9的倍数，而$9N+9k$一定是9的倍数

所以我们只需要求出最小的$k$，使得$9N+9k$的数位和小于等于$9k$即可

由数学归纳法不难证明，本题中$k\leq len(N)$，所以我们只需要枚举$k=1\cdots 5e5$，只要维护一个高精度+即可，复杂度是担此操作均摊$O(1)$，总复杂度$O(n)$

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

char s[1000010];int a[1000010];

int main(){

	scanf("%s",s);int n=strlen(s),i,j,sum=0,k;

	for(i=1;i<=n;i++) a[i]=(s[n-i]-'0')*9;

	for(i=1;i<=n;i++){

		a[i+1]+=a[i]/10;a[i]%=10;

	}

	if(a[n+1]) n++;

	for(i=1;i<=n;i++) sum+=a[i];

	for(k=1;k<=n*10;k++){

		a[1]+=9;sum+=9;

		j=1;

		while(j<=n){

			if(a[j]<10) break;

			sum-=10;a[j]-=10;

			sum++;a[j+1]++;

			j++;

			if(j==n&&a[j+1]) n++;//别忘了有可能加一位

		}

		if(sum<=9*k){//注意这里一定不要写成等于了

			printf("%d\n",k);return 0;

		}

	}

}