ABC083B - Some Sums

GitHub跳转原题关系图返回列表

遍历 1..N，递归拆位计算各位数字之和，筛选在 [A,B] 内的数并求和。

OJ: atcoder

题目 ID: abc083_b

难度:入门

标签:haskell

日期: 2026-07-10 11:27

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

求 11 到 NN 中，各位数字之和在 [A,B][A,B] 内的所有数的总和。

思路

遍历 1..N1..N，递归拆位计算各位和，筛选符合条件的数累加。

代码

haskell
{-
 Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 rainboy的学习导航网站: https://idx.roj.ac.cn
 create_at: 2026-07-10 14:18
 update_at: 2026-07-10 14:18
-}
digitSum 0 = 0
digitSum n = n `mod` 10 + digitSum (n `div` 10 )

main = do
    [n,a,b] <- map read . words <$> getContents :: IO [Int]
    let l = [ x | x <- [1..n], let t = digitSum x , t >= a , t <=b ]
    print $ sum l

复杂度

时间复杂度 O(Nlog⁡10N)O(N \log_{10} N)，空间复杂度 O(1)O(1)。

总结

递归拆位 + 列表推导式 + sum 求和。