多元一次不定方程的强力算法:同余筛数法

今天朋友问了一个问题, 已知正整数 s 和正整数集合 j1 j2 j3… jn , 未知正整数 k1 k2 k3…kn,使得s = j1 * k1 + j2 * k2 + j3 * k3 + jn * kn,要求 k1 k2 k3…kn的值。 这个凑单时经常用到,如定好每件商品的单价以及总金额,要求出每样商品的数量。 一个简单的例子 看一个简单的例子,有若干的 1块,2块,5块的纸币,凑100块钱。 即 1x + 2y + 5*z = 100 这个是多元一次不定方程。这在数论里面有研究,通过通解来求解特定范围的解理论上虽然可行,但遗憾的是其求解效率几乎与穷举法相当的。 同余筛数法 下面介绍一种比上述方案更快速的强力快速算法。这是一种基于同余理论的快速算法,同余筛数法。 原理 我们知道二元不定方程 a * x + b * y = c 其实是与同余方程 a * x = c (mod b) 等价的。 同理对于三元不定方程 a * x + b * y + c * z = d ,实际上也可以理解成 a * X = p (mod c),b * Y = q (mod c),设d = d' (mod c),则有 p + q = d' (mod d)。 为什么会有这样的结论?原因很简单:d - a * x + b * y = c * t0 + d' - a * c * t - p - b * c * t' - q = c * z = 0 (mod c)。...

March 29, 2022 · 1 分钟 · ming

manjaro-setup

manjaro 设置 切换到 manjaro 已经好几年, 有时换机器或者重装系统总有几个相同的步骤要设置,故写此文记录一下。 针对中文环境,版本为 Manjaro 21.2.3 Qonos KDE。 设置 manjaro 镜像源为中国 可以在 Pamac 图形界面中直接设置。 设置显示缩放 如果是高分辨率屏幕,可以在系统 > 显示 中设置全局缩放,这样看上去字体不会太小。 时间同步 虚拟机和宿主机时间相差 8 个小时,可以在 manjaro 时间设置页面 “勾选自动设定日期和时间”, 启用时间同步后即可修复该问题。 安装中文输入法 #安装 Fcitx5主体、配置工具、输入法引擎及中文输入法模块,可参考 https://www.bilibili.com/read/cv14016623 sudo pacman -S fcitx5-im fcitx5-chinese-addons fcitx5-qt fcitx5-gtk sudo vim ~/.pam_environment #加入以下内容(中间是一个 Tab键,一般情况下只需要前三行) GTK_IM_MODULE DEFAULT=fcitx QT_IM_MODULE DEFAULT=fcitx XMODIFIERS DEFAULT=\@im=fcitx INPUT_METHOD DEFAULT=fcitx SDL_IM_MODULE DEFAULT=fcitx #安装中文维基百科词库 sudo pacman -S fcitx5-pinyin-zhwiki 配置完成后,建议注销或重启一下。 安装 aur 助手 AUR 是针对基于 Arch 的 Linux 发行版用户的社区驱动的仓库,很多官方仓库没有收录的软件包要从 AUR安装。 安装 yay 后可以方便的从 AUR 安装软件。...

February 7, 2022 · 1 分钟 · ming

tidb tools

很开心最近以不错的成绩过了 tidb 的 PCTA 认证, 该认证是 tidb 的基础运维能力认证. 除了理解 tidb 的基本概念, 使用 tiup 部署管理集群, 还有很大一块就是学会使用TiDB生态工具,进行数据迁移和校验,例如:数据迁入、全量导出、全量导入、备份恢复、校验等等。 它们的特性更有不同, 如上游下游是啥, 速度和数据量, 是否需要停机或者只读, 是否支持异构, 兼容的版本, 是否需要额外部署组件等, 理解它们的异同及各自的使用场景, 是考试中容易丢分的点, 故结合 301 视频和官方文档, 稍作整理如下. BR BR 全称 backup & restore, 是 tidb 分布式备份恢复的命令行工具, 用于对 tidb 集群进行数据备份和恢复. BR 属于物理备份,数据由 TiKV 从各个 region 的 leader 生成 SST 格式的 KV 数据,它是专用的 TiDB 格式,不能用于 MySQL 的还原。TiKV 进行数据还原时,没有固定的节点对应关系,所有的节点都需要访问完整的数据,所以 BR 最好使用 NFS/S3 共享存储存储。支持按库, 表过滤, 支持全量增量, 支持限速. Dumpling 数据导出工具 dumpling 可以把存储在 tidb/mysql 中的数据导出为 sql 或者 csv, 可以用于完成逻辑上的全量备份或者导出....

December 5, 2021 · 2 分钟 · ming

tidb 与 tdsql 比较  [draft]

tidb 是优秀的国产开源分布式数据库, 因为其开放和拥抱开源的态度, 我也得以参与其中, 成为社区一员. tidb 到底咋样, 有没有它说的那么厉害, 有啥优缺点, 需要找一个合适的对手来比较. 通过比较也可以取长补短, 互相学习. 因为我用腾讯的产品比较多, 也有同学参与了 tdsql 的开发, 对 tdsql 有少量的了解, 所以找它作为比较对象. 首先申明, 我不是数据库专家, 仅仅是入行不久的爱好者, 也没有深度参与两家数据库的开发工作, 所以仅仅是一个仰望者的视角, 会做尽量多的调研, 但主要基于双方公开资料. 简介 tidb tidb 是 pingcap 公司的产品, 创始人刘奇, 黄东旭, 崔秋 均为技术出身, 有多个流行的开源项目, 这可能为 tidb 打下了开放和开源的基因. tidb 历史 先来说说数据库的发展史. 架构 特性 优缺点 生态 总结 参考 腾讯云TDSQL助力金融核心系统数字化转型 TDSQL inside之路 腾讯云TDSQL高可用技术解决方案介绍 TDSQL怎么实现迁移TDSQL云原生

October 10, 2021 · 1 分钟 · ming

some tips for golang range

There are 2 types of range, with index and without index. Let’s see an example for range with index. func TestRangeWithIndex(t *testing.T) { rows := []struct{ index int }{{index: 0}, {index: 1}, {index: 2}} for _, row := range rows { row.index += 10 } for i, row := range rows { require.Equal(t, i+10, row.index) } } the output is: Error Trace: version_test.go:39 Error: Not equal: expected: 10 actual : 0 Test: TestShowRangeWithIndex Above test fails since when range with index, the loop iterator variable is the same instance of the variable with a clone of iteration target value....

September 17, 2021 · 3 分钟 · ming

前端画图调研

最近公司有个项目有电力图方面的图形编辑和可视化需求, 包括: 图元(设备、线、文字等)的编辑(拖曳,分布,组合)、保存、查找等操作. 图的编辑(拖曳,分布,组合)、保存、查找等操作 图与档案运行状态的联动 通过配置的档案信息自动生成监视图形。 我做了一些调研并基于此做了一些开发工作, 目前还算成功,把调研过程和成果简单分享一下。 调研 支持现代浏览器(chrome, firefox), 不支持 ie8 和 ie11 需要: 2d, canvas, webgl, 画布状态, 不需要: 3d, 碰撞检测, 游戏引擎 主要考虑流行度成熟度(star), 商业友好(license), 特性满足需求, 生态好, 学习成本低(文档好)。 经考察, 最终选择 topology 这个开源项目, 加 nuxtjs 实现. 开源软件 学习和开发成本, 自有产权 topology, 可视化在线绘图工具, 2.7k star, license MIT 基于开源内核实现的绘图编辑器topology-vue 使用指南 X6 是 AntV 旗下的图编辑引擎, 1.6k star, license MIT antv家族 pixi.js, The HTML5 Creation Engine, 32.4k star, license MIT...

September 13, 2021 · 1 分钟 · ming

来自新手的 tidb 贡献指南

学习 go 之后常年关注 go 生态, 除了 docker, k8s 这些云原生领域的顶梁柱, 国内的 newsql 数据库 tidb 也很快进入关注列表。 在对 tidb 有了更多的了解之后, 对它的兴趣也越大, 如: 云原生的 newsql 解决方案 完全开源,开放的生态和社区 在几年前选型时,就选择了 sql 层 go, 存储层 rust 的双语方案,魄力 国人做的。 终于有国人在 操作系统, 数据库, 编译器 这 3 大基础软件领域做出了有一定成绩,且有完全自主知识产权的产品了(而不是各种魔改)! 虽然我对它兴趣浓厚, 想深入的了解学习一下, 却没有想过要参与到它的开发中去, 最大的原因可能是认为数据库的开发很难,我的 go 也刚学不久 等, 直到我看到 tison 的一篇 vlog 一分钟成为 TiDB 贡献者, 我抱着试试的态度,开始了 tidb 的 contribute 之旅。 虽然只是开始,但也涨了不少知识,踩了一些坑,趁热写这么一篇文章,希望对后来的新人有帮助。 概述 tidb 分布式数据库是个庞大的系统,从核心到外围,可以大概分为: tidb(go) + tikv(rust),除了同名主仓库,还有好些依赖组件在他们各自的仓库 安装,监控,数据迁移等官方工具, 如 tiup, dm 等 文档 客户服务,论坛等 一个庞大的系统必然有各种各样任务,他们的难度是不一样的,小到修改一个错别字,写一篇使用心得,都可以算是贡献。 我的 contribute 之路也是从一个小小的测试重构开始的。...

August 8, 2021 · 2 分钟 · ming

golang i18n的不同思路

传统的解决方案 i18n是软件开发中常见的一个需求, 很多流行的开发框架如 ruby on rails, springboot 对它有内置的支持。 rails 的 i18n 是其中的佼佼者, 我们看看它解决了哪些问题,是如何解决的。 i18n 资源文件 通常开发者需要按照框架的约定创建资源文件,一般会在目录或文件名中包含如 es, en 等 locale 信息,方便框架按需加载。 |---books |-----es.yml |-----en.yml |---users |-----es.yml |-----en.yml key 的定义和查找优先级 通常每个翻译文本会对应一个有意义的key,通过 key + locale 的组合得到当前 locale 下的翻译文本. I18n.t 'activerecord.models.user' # => 'Customer' I18n.t 'activerecord.models.user' # => '客户' en: activerecord: models: user: "Customer" attributes: user: login: "Login" zh: activerecord: models: user: "客户" attributes: user: login: "登陆" 当项目到一定规模, key 的数量很多时,key 的命名就显得格外重要,否则重用 key 时很难查找。 而且除了用户自定义的 key, 框架一些内置的 key 如日期, 错误消息等, 也需要用户提供翻译。 所以 key 的命名 rails 也做了约定,如下...

June 30, 2021 · 2 分钟 · ming

博客迁移到 hugo

折腾博客的那些事 2012年开始折腾博客,转眼已经8个年头,一开始用的 jekyll, 期间在简书上面也写了少量文章,再基于 halo 搭建了动态站点 topcoder, 然后最近受 苏洋的博客 启发基于 hugo 搭建了本博客。 hola 是带后端的博客程序, 本意是搞一点动态内容和互动进去, 可是本身的懒惰导致写博客都没有好好坚持, 动态站点一年多也跟一个静态站点差不多,没什么动态内容。 而像 苏洋的博客 这样的静态站点, 内容却挺吸引我, 可见重要的是内容。 选型 go 是一门有活力有前途的语言,我最近也正在学习, 这是我选择 hugo 的一个原因, 另一个原因是 hugo 确实很快, 我现在80多篇文章 300 毫米左右, 估计 10000 篇博客以内, 都在一秒内就够了。 Start building sites … | ZH -------------------+------ Pages | 161 Paginator pages | 17 Non-page files | 0 Static files | 1 Processed images | 0 Aliases | 41 Sitemaps | 1 Cleaned | 0 Built in 362 ms 但它的模板语法写起来还是挺繁琐, 做主题, 做静态站点这块前端有一定成本。...

March 27, 2021 · 1 分钟 · ming

multispeack 简单研究

multispeack 简单研究 MultiSpeak Specification 是一个广泛用于北美企业和公用事业部门(如水电)的企业应用互联规范,帮助它们定义接口, 让不同供应商的软件可以不需额外开发接口就可以互联。 为了达成这个目标, 该规范有3个主要部分组成: 通用数据模型 通用数据模型是对某一业务流程的数据的规范,如停电事件模型。通用数据模型使用 XML 描述。 消息结构 为了交换数据,需要定义消息结构,MultiSpeak 使用 WSDL 来描述消息, 用 web service 来交换消息, 支持实时的,或者批量。 业务流程 不同的 web service 调用组成了单个业务流程中的一个步骤,多个步骤组成了一个业务流程, 多个业务流程组成了一个完整的业务。 一个业务流程 和 一个完整的业务分别在模块用户案例和完整用户案例中描述。 使用情况 超过 90 家企业和公用事业部门贡献和使用该规范, 有超过 360 家经过训练的软件供应商 需要注册会员, 不知道是否收费, 未注册尝试 下载规范文档需要收费, 按模块, 每个模块 300 美金, 页面上共 12 个收费模块, 3个免费模块, 详情 费用情况 未见开源产品, 它有一个官方市场, 有一些产品供购买,包括:...

March 19, 2021 · 2 分钟 · ming