AGC011-E Increasing Numbers

2024-09-06 19:38:18

题意

给定一个数\(n\)，\(n≤10^{500,000}\)，问\(n\)最少可以拆分成几个不降数的和。一个不降数是在十进制位下，从高位往低位看，每个数都不会比高位的数更小的数

做法

不降数可以拆成若干个形似\(1111...111\)的数相加
位数为\(l\)的全\(1\)数可以写成\(\dfrac{10^{l+1}-1}{9}\)

\(N=\sum\limits_{i=1}^k \dfrac{10^{a_i}-1}{9}\)
通过手玩可以进一步发现充分条件：\(9|k\)

写成\(N+9k=\sum\limits_{i=1}^{9k}10^{a_i}\)
枚举\(k\)，判断\(N+9k\)的数位之和是否小于等于\(9k\)就好了

高精度加\(1\)复杂度是均摊的，\(O(位数)\)

最新文章

热门文章