首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >2026-06-25:给定范围内 K 位数字之和。用go语言,给定三个整数 l、r、k。 我们要考虑所有恰好有 k 位的整数,这些整数的每一位数字都是

2026-06-25:给定范围内 K 位数字之和。用go语言,给定三个整数 l、r、k。 我们要考虑所有恰好有 k 位的整数,这些整数的每一位数字都是

作者头像
福大大架构师每日一题
发布2026-06-25 17:42:18
发布2026-06-25 17:42:18
150
举报

2026-06-25:给定范围内 K 位数字之和。用go语言,给定三个整数 l、r、k。

我们要考虑所有恰好有 k 位的整数,这些整数的每一位数字都是这样选出来的:

对每一位,从区间 [l, r](包含端点)的数字中独立随机选择一个作为该位的数字;如果 [l, r] 内包含 0,那么允许出现前导零(因此不要求最高位不能为 0)。

把所有符合条件的 k 位数全部列出,然后计算它们的总和。

由于结果可能非常大,请对 1000000007 取模,返回最终结果。

0 <= l <= r <= 9。

1 <= k <= 1000000000。

输入: l = 5, r = 5, k = 10。

输出: 555555520。

解释:

5555555555 是唯一一个由范围 [5, 5] 内 k = 10 位数字组成的有效数字。

总和为 5555555555 % 1000000007 = 555555520。

题目来自力扣3855。

一、数学推导分步详解(对应代码sumOfNumbers公式来源)

步骤1:计算单一位的数字平均值

区间 [l, r] 数字总和: 其中 ,代表每一位可选数字总个数。 每位数字的期望(平均取值):

步骤2:拆分k位数的位权贡献(核心思想)

一个k位数,从右到左各位权值依次是: 所有合法数字总和 = 每一位单独贡献之和,每一位贡献相互独立,可分开计算再相加。

单一位(固定某一位置,比如第t位,权值)的总贡献

  1. 1. 该位所有可选数字总和:
  2. 2. 其余k-1位每一位都有m种选择,总组合数:
  3. 3. 该位权值: 所以单个位置总贡献:

所有k个位置总贡献求和

总和 提取公共因子 :

等比数列求和: 代入总和公式: 合并分母:

步骤3:模意义下除法转换为乘法逆元

模数 mod=1e9+7 是质数,根据费马小定理: 对不被mod整除的x, 原式除以18等价于乘以18的模逆元:。 同时 可能为负数(模运算下),所以加mod再取模保证正数:。

最终模运算公式(和代码完全对应):

\begin{align}Total \pmod{mod}&= \Big[(l+r) \cdot m \pmod{mod}\Big] \&\cdot \Big[(10^k - 1 + mod) \pmod{mod}\Big] \pmod{mod} \&\cdot inv_{18} \pmod{mod} \&\cdot \Big[m^{k-1} \pmod{mod}\Big] \pmod{mod}\end{align}

二、代码执行分步流程(以输入l=5,r=5,k=10举例)

阶段1:预处理常量与基础变量

  1. 1. 固定模数 mod = 1000000007
  2. 2. 入参 l=5,r=5,k=10;
  3. 3. 计算每一位可选数字总数:。

阶段2:分项逐个计算(按公式乘法顺序)

分项A:

分项B:,负数修正

调用快速幂 pow(10, 10) 算出 ; 计算 ,再加mod避免负数:,得到9999999999。

分项C:18的模逆元

程序每次计算都会调用 pow(18, mod-2),预先算出18在模1e9+7下的乘法逆元,记为inv18。

分项D:

m=1,任意次幂结果都是1,调用快速幂 pow(1, 9) 得到1。

阶段3:逐项模乘合并结果

严格按顺序连续相乘,每一步都对mod取模,防止数值溢出:

  1. 1. 先乘A × B,模mod;
  2. 2. 中间结果 × inv18,模mod;
  3. 3. 中间结果 × D,模mod; 最终得到总和模mod的值 555555520。

阶段4:输出结果

打印合并后的模值,匹配样例输出。

三、核心工具:快速幂pow(x, n)详细执行逻辑

函数作用:快速计算 ,n可高达1e9,二进制分解幂次。

  1. 1. 初始化结果res=1;
  2. 2. 循环条件 n>0,每次将n整除2(右移一位):
    • • 若当前n二进制最低位为1(n%2==1):把res = res * x % mod,把当前底数乘入结果;
    • • 更新底数:x = x * x % mod(底数平方,对应二进制高位);
  3. 3. n缩减到0后返回res。

以样例中pow(10,10)为例: 10二进制是1010,循环仅执行log₂10≈4次,无需循环10次。

四、总时间复杂度、额外空间复杂度分析

1. 时间复杂度

程序内一共调用3次快速幂:

  1. 1. :幂次k最大1e9,循环次数 ;
  2. 2. :mod固定1e9+7,指数固定,循环次数 ,为常数;
  3. 3. :幂次k最大1e9,循环次数 。

其余加减乘、变量赋值都是O(1)常数操作。 是固定常量可忽略,总时间复杂度:

2. 额外空间复杂度

  1. 1. 仅使用固定数量局部变量(res、x、n、m、各项中间乘积);
  2. 2. 快速幂为迭代实现,无递归栈、无数组、无动态内存;
  3. 3. 不随k、l、r输入规模扩张。

总额外空间复杂度: (常数空间)

Go完整代码如下:

.

代码语言:javascript
复制
package main

import (
    "fmt"
)

const mod = 1_000_000_007

func pow(x, n int)int {
    res := 1
    for ; n > 0; n /= 2 {
        if n%2 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

func sumOfNumbers(l, r, k int)int {
    m := r - l + 1
    return (l + r) * m * (pow(10, k) - 1 + mod) % mod * pow(18, mod-2) % mod * pow(m, k-1) % mod
}

func main() {
    l := 5
    r := 5
    k := 10
    result := sumOfNumbers(l, r, k)
    fmt.Println(result)
}
在这里插入图片描述
在这里插入图片描述

Python完整代码如下:

.

代码语言:javascript
复制
# -*-coding:utf-8-*-

MOD = 1_000_000_007

def pow_mod(x, n):
    """快速幂取模"""
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = res * x % MOD
        x = x * x % MOD
        n //= 2
    return res

def sum_of_numbers(l, r, k):
    m = r - l + 1
    # (l + r) * m * (10^k - 1) * inv(18) * m^(k-1) mod MOD
    return (l + r) * m % MOD * (pow_mod(10, k) - 1 + MOD) % MOD * pow_mod(18, MOD - 2) % MOD * pow_mod(m, k - 1) % MOD

def main():
    l = 5
    r = 5
    k = 10
    result = sum_of_numbers(l, r, k)
    print(result)

if __name__ == "__main__":
    main()
在这里插入图片描述
在这里插入图片描述

C++完整代码如下:

.

代码语言:javascript
复制
#include <iostream>
using namespace std;

const long long MOD = 1000000007LL;

long long pow_mod(long long x, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
        n /= 2;
    }
    return res;
}

long long sumOfNumbers(long long l, long long r, long long k) {
    long long m = r - l + 1;
    long long result = (l + r) % MOD;
    result = result * m % MOD;
    result = result * ((pow_mod(10, k) - 1 + MOD) % MOD) % MOD;
    result = result * pow_mod(18, MOD - 2) % MOD;
    result = result * pow_mod(m, k - 1) % MOD;
    return result;
}

int main() {
    long long l = 5;
    long long r = 5;
    long long k = 10;
    long long result = sumOfNumbers(l, r, k);
    cout << result << endl;
    return0;
}
在这里插入图片描述
在这里插入图片描述

·


我们相信人工智能为普通人提供了一种“增强工具”,并致力于分享全方位的AI知识。在这里,您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。

·

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2026-06-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、数学推导分步详解(对应代码sumOfNumbers公式来源)
    • 步骤1:计算单一位的数字平均值
    • 步骤2:拆分k位数的位权贡献(核心思想)
      • 单一位(固定某一位置,比如第t位,权值)的总贡献
      • 所有k个位置总贡献求和
    • 步骤3:模意义下除法转换为乘法逆元
  • 二、代码执行分步流程(以输入l=5,r=5,k=10举例)
    • 阶段1:预处理常量与基础变量
    • 阶段2:分项逐个计算(按公式乘法顺序)
      • 分项A:
      • 分项B:,负数修正
      • 分项C:18的模逆元
      • 分项D:
    • 阶段3:逐项模乘合并结果
    • 阶段4:输出结果
  • 三、核心工具:快速幂pow(x, n)详细执行逻辑
  • 四、总时间复杂度、额外空间复杂度分析
    • 1. 时间复杂度
    • 2. 额外空间复杂度
  • Go完整代码如下:
  • Python完整代码如下:
  • C++完整代码如下:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档