Warning: session_start(): open(/tmp/sess_87711d46cf6090fe2475dc2b09bf4113, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/8fe637ac40e9dfa91f93fbcd08d065e4.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
==== 题面描述 ====
给定一个 $n$ ，定义 $f_k{(n)}$ 表示 $n$ 在 $k$ 进制下每位的和，求在 $2 \le k \le K$ 时，$f_k{(n)}$ 的最小值。
$n,K \le 10^{36}$
==== 题解 ====
考虑对进制进行分治。
对于小于等于 $10000$ 的进制，直接暴力算出其贡献；对于大于 $10000$ 的进制，如果其可以作为最优解出现，那么一定满足存在一组 $a,b,d$ ，使得其是最大的满足 $a*x^d+b*x^{d-1}\le n$ 的。注意到这里的变量可枚举的范围均很小，所以暴力枚举即可，稍微注意一点优化就可以通过此题。