首页/新闻资讯/正文详情

LeetCode 1015:由1组成的最小整数与模运算应用

发布时间:2026/11/5 21:27:49 来源:云帆数科 栏目:资讯中心
LeetCode 1015:由1组成的最小整数与模运算应用
1. 问题背景与理解Smallest Integer Divisible by K 是 LeetCode 上一道关于数论和模运算的中等难度题目。题目要求找出由数字1组成的最小的正整数使其能够被给定的正整数K整除。例如当K3时答案是111因为111÷337。这类问题在实际应用中可能出现在密码学、哈希算法设计或循环检测等场景。理解这个问题的关键在于掌握模运算的基本性质特别是循环节的概念。2. 核心算法思路2.1 数学原理分析我们需要找到一个由n个1组成的数字N使得N ≡ 0 mod K。这个数字可以表示为 N (10^n - 1)/9因此我们需要找到最小的n使得 (10^n - 1)/9 ≡ 0 mod K 即 10^n ≡ 1 mod 9K根据欧拉定理如果10和9K互质那么解一定存在且n ≤ φ(9K)其中φ是欧拉函数。如果不互质则无解。2.2 算法实现步骤检查K是否为2或5的倍数如果是则无解因为任何由1组成的数都不可能被2或5整除初始化余数r0进行最多K次迭代计算新余数r (10 * r 1) % K如果r 0返回当前迭代次数如果K次迭代后仍未找到解返回-13. C语言实现详解3.1 完整代码实现int smallestRepunitDivByK(int K) { if (K % 2 0 || K % 5 0) { return -1; } int remainder 0; for (int length 1; length K; length) { remainder (remainder * 10 1) % K; if (remainder 0) { return length; } } return -1; }3.2 关键代码解析边界条件检查if (K % 2 0 || K % 5 0) { return -1; }这是基于数学性质任何由1组成的数都不可能被2或5整除。模运算迭代remainder (remainder * 10 1) % K;这个表达式巧妙地避免了直接计算大数而是通过模运算的性质逐步计算余数。终止条件if (remainder 0) { return length; }当余数为0时说明找到了满足条件的数。4. 算法复杂度分析时间复杂度O(K)因为最多进行K次迭代空间复杂度O(1)只使用了常数级别的额外空间实际上根据数学理论解的上限是φ(9K)通常远小于K所以实际运行时间往往比O(K)更好。5. 常见问题与调试技巧5.1 为什么迭代次数限制为K次根据鸽巢原理在K次迭代中余数必然会出现重复。如果前K次迭代都没有找到余数为0的情况则说明无解。5.2 如何处理大数溢出问题这是本题的关键技巧。直接计算由1组成的大数会导致溢出。我们通过模运算的性质只跟踪余数而不是完整的数值新余数 (旧余数 × 10 1) % K5.3 测试用例建议常规情况K1应返回1K3应返回3111÷337K7应返回6111111÷715873边界情况K0根据题目约束K≥1K2或5的倍数应返回-1大质数如K997应返回9966. 算法优化思路虽然这个算法已经相当高效但还可以进一步优化提前终止当余数开始循环时即出现之前出现过的余数可以立即返回-1数学优化利用K的因数分解信息可以更精确地估计解的上限7. 实际应用场景这类算法在以下场景中有实际应用循环小数检测确定分数1/K的循环节长度哈希算法设计需要均匀分布的哈希值时伪随机数生成寻找合适的模数8. 扩展思考这个问题可以扩展到其他进制在b进制下找出由1组成的最小的数能被K整除解法类似只需将代码中的10改为b即可对于特别大的K如1e9以上可以考虑使用快速幂算法来优化模运算过程。

相关推荐

工业物联网云平台架构设计与Java开发实战
工业物联网云平台架构设计与Java开发实战

1. 工业物联网云平台核心架构解析这个基于Java开发的物联网云平台,本质上构建了一个工业设备数字化的中枢神经系统。它通过四层架构实现全链路管控:设备连接层:采用MQTT/Modbus等多协议适配器,像万能转换插头一样兼容各类工业设备… · 2026/11/5 4:44:11

单核CPU如何支持Java多线程?原理与实践解析
单核CPU如何支持Java多线程?原理与实践解析

1. 面试题背后的技术本质 当面试官抛出"单核CPU支持Java多线程吗?为什么?"这个问题时,实际上是在考察候选人对以下三个维度的理解深度: 操作系统层面的线程调度机制 JVM的线程模型实现原理 并发编程的抽象层次 1.1… · 2026/11/3 7:58:45

AI教材编写:低查重技术架构与实战策略
AI教材编写:低查重技术架构与实战策略

1. AI教材编写的行业痛点与查重挑战教材编写领域长期存在两个核心矛盾:内容质量与生产效率的平衡、知识体系完整性与查重率控制的博弈。传统教材编写模式下,教育工作者需要投入数百小时进行资料收集、内容编排和语言润色,而最终成稿的查重率往… · 2026/11/3 12:36:03

EasyU优启通PE维护盘实战指南:制作、启动与核心操作全解析
EasyU优启通PE维护盘实战指南:制作、启动与核心操作全解析

1. 为什么一个PE维护盘值得单独拿出来聊装系统、修引导、救数据、清病毒,这些活儿但凡干过几次的人都知道,真正决定效率的往往不是你手速多快,而是手边那套PE环境靠不靠谱。EasyU(圈内习惯叫优启通)就是在这个场景下被… · 2026/11/5 16:49:35

Rust原来很简单二:所有权系统
Rust原来很简单二:所有权系统

Part 2 核心篇 —— 所有权系统 本篇覆盖 第 6 ~ 10 章:所有权、借用与引用、生命周期、字符串与切片、内存模型。 ⚠️ 这是全书最重要的一篇。 把它吃透,Rust 从此“很简单”;跳过它,你会处处碰壁。请慢下来,动手敲每一段代码。 第 6 章 所有权:Rust 的第一性原理 6… · 2026/11/5 16:26:08

基于Hadoop+Spark的民宿智能推荐系统设计与实现
基于Hadoop+Spark的民宿智能推荐系统设计与实现

1. 项目概述:大数据时代的民宿智能推荐这个毕业设计项目融合了当前大数据领域最主流的技术栈,构建了一个完整的民宿推荐系统解决方案。作为一名长期从事大数据系统开发的工程师,我认为这个选题非常贴合实际应用场景——随着旅游业的复苏和共享… · 2026/11/5 14:59:25

ADS122U04IPWR+STM32F427ZI工业级温度测量信号链设计
ADS122U04IPWR+STM32F427ZI工业级温度测量信号链设计

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 14:10:41

UART接口24位ADC搭配RS485,解决远距离温度监控难题
UART接口24位ADC搭配RS485,解决远距离温度监控难题

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 14:10:41

UART接口24位ADC搭配PIC18F46K22的RTD与热电偶测温实践
UART接口24位ADC搭配PIC18F46K22的RTD与热电偶测温实践

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 14:10:41

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:07

多智能体协作系统架构设计与实践优化
多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时,Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南:从原理到部署微调的全链路路线
大模型系统性入门实战指南:从原理到部署微调的全链路路线

提到大模型的系统性入门,我先说个结论:这事真不难,难的是资料太散、路线太多,今天这个框架明天那个工具,新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践
鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师,我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码,在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:07

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码