`
luotuoass
  • 浏览: 635095 次
文章分类
社区版块
存档分类
最新评论

实用算法实现-第 27 篇 中国余数定理

 
阅读更多

27.1 中国余数定理

定理:对任意n > 1,如果gcd(a, n) = 1,则方程a • x ≡ 1(mod n)对模n有唯一解,否则方程无解。若方程有解,x可以表示为(a^-1) mod n,x可以由欧几里德算法的扩广形式求出。

设n1, n2, ..., nk两两互质,n = n1• n2 • ... • nk

定义:mi = n1• n2 • ... • ni-1 • ni+1 • ... • nk

定义:ci = mi • (mi^-1 mod ni)

定义:a ≡ (a1•c1 + a2• c2 + ...+ak•ck) (mod n)

可以证明:a ≡ ai (mod ni)

证明如下:

ci = mi • (mi^-1 mod ni) 故此ci ≡ 1 (mod ni)

又由mi ≡ 0 (mod nj) j= 1, 2, ..., i-1, i+1, ...k

故此 mi • (mi^-1 mod ni) ≡ 0 (mod nj) j =1, 2, ..., i-1, i+1, ...k

故此ci ≡ 0 (mod nj) j = 1, 2, ...,i-1, i+1, ...k

由 ci ≡ 0 (mod nj) j = 1, 2, ..., i-1, i+1, ...k

ci ≡ 1 (mod nj) j = i

可知ci和(0, 0, ..., 0, 1, 0, ..., 0)有一一对应的关系。

故此a ≡ ai • ci (mod ni)

≡ ai • mi(mi^-1 mod ni) (mod ni)

≡ ai (mod ni)

由上面证明可知:对于两两互质的n1, n2, ..., nk,若已知a1, a2, ..., ak,则可以求出a (mod n),使得ai = a (mod ni)。即a和(a1, a2, ..., ak)一一对应。

由中国余数定理有:

推论:如果n1, n2, ..., nk两两互质,n=n1 • n2 • ... • nk,则对所有整数x和a(i = 1, 2, ..., k), 有x = a(mod ni),当且仅当x = a(mod n)。

27.1.1实例

PKU JudgeOnline, 1006, Biorhythms.

27.1.2问题描述

一个人体力、情绪、智力的波动周期为23,28,33天,给定每种状态达到最高点分别为第p, e, i天,从第d天开始,过多少天后会达到三者的最高点。

27.1.3输入

00 0 0

00 0 100

520 34 325

45 6 7

283102 23 320

203301 203 40

-1 -1 -1 -1

27.1.4输出

Case1: the next triple peak occurs in 21252 days.

Case2: the next triple peak occurs in 21152 days.

Case3: the next triple peak occurs in 19575 days.

Case4: the next triple peak occurs in 16994 days.

Case5: the next triple peak occurs in 8910 days.

Case6: the next triple peak occurs in 10789 days.

27.1.5分析

这里23,28,33互质,所以可以用中国剩余定理的这个推论。

先求出mi,再根据欧几里德算法的扩广形式求出((mi^-1) mod ni),再求出ci。将ci作为常数存起来,然后根据公式求出a就可以了。

27.1.6程序


27.2 实例

PKU JudgeOnline, 1006, Biorhythms.

本文章欢迎转载,请保留原始博客链接http://blog.csdn.net/fsdev/article

分享到:
评论

相关推荐

    云计算-基于中国余数定理及全相位理论的高精度频率估计算法研究.pdf

    云计算-基于中国余数定理及全相位理论的高精度频率估计算法研究.pdf

    Python实现的中国剩余定理算法示例

    本文实例讲述了Python实现的中国剩余定理算法。分享给大家供大家参考,具体如下: 中国剩余定理(Chinese Remainder Theorem-CRT):又称孙子定理,是数论中的一个定理。即如果一个人知道了一个数n被多个整数相除得到...

    中国剩余定理孙子定理-suziTheorem.zip

    中国剩余定理孙子定理-suziTheorem.zip 根据韩信点兵典故写的算法,复杂度为O.参考链接: en.wikipedia.org/wiki/Chinese_remainder_theorem

    n-chinese-remainders:中国余数定理-渐进求解,n-soln,其他-开源

    “中国余数”可以快速求解模量方程组。 crtwo是对Mathematica版本的改进。 crtwo:一次解决一对中文余数(使用gcd),但仍然很快。 这意味着crtwo与课本soln不同,它一次使用一种算法来求解一个mod方程或使一个方程...

    中国剩余定理Matlab代码-Adding-Large-numbers-using-Chinese-Remainder-Theorem:使用中

    中国剩余定理Matlab代码使用中国余数定理将两个大数相加 问题陈述 问题编号27-编写MATLAB代码以使用中文余数定理添加超过计算机字大小的大整数。 团队成员 塔伦·阿南德(Tarun Anand)-16CO147 阿奇特·潘迪-16CO...

    使用Winograd算法实现不规则长度DFT———在多载波调制系统( OFDM)中不规则长度 FFT的一种实现方法 (2007年)

    介绍了二维卷积算法 Agarwal-Cooley、包括中国余数定理、小点数的 Winograd卷积算法和克罗内克积;在介绍算法的同时穿插 11点 FFT的推导,先计算 2点和 5点Winograd卷积,之后得到 10点卷积,最后得出 11点 FFT。

    基于中国余数定理的欠采样下余弦信号的频率估计

    基于中国余数定理的重构算法的信号频率估计是近年来信号处理、电磁学以及光学等领域的前沿问题,但目前这些研究仅限于对复指数信号做粗略频率估计.因而,本文把基于中国余数定理的频率估计从复指数信号粗估计拓展到实...

    基于余数定理的低复杂度渐进边增长算法

    我们首先通过PEG算法构造长度为n 1的基本LDPC码,然后通过中文余数定理(CRT)将这个LDPC码扩展为长度为n的LDPC码,其中n≥n 1来解决这个问题。此方法增加了用PEG算法生成的LDPC代码的代码长度,而不减小其周长。...

    算法导论中文版

     31.5 中国余数定理  31.6 元素的幂  31.7 RSA公钥加密系统  31.8 素数的测试  31.9 整数的因子分解  思考题  本章注记 第32章 字符串匹配  32.1 朴素字符串匹配算法  32.2 Rabin\Karp算法  32.3...

    时空欠采样下多个信号的频率和DOA联合估计.pdf

    针对时-空欠采样条件下多个入射信号的频率和波达方向(DOA)联合估计问题,提出了基于中国余数定理(CRT)的估计算法。利用稀疏分布的非均匀线阵对同时到达的多个入射信号进行多路的并行欠采样,借助AM估计器的谱...

    算法导论(part2)

    本书是原书的第2版,在第1版的基础之上增加了一些新的内容,涉及算法的作用、概率分析和随机化算法、线性规划,以及对第1版中详尽的、几乎涉及到每一小节的修订。这些修订看似细微,实际上非常重要。书中引入了...

    ACM 算法模板集

    7. Chinese Remainder Theorem中国余数定理(互素于非互素) 8. Euler Function欧拉函数 9. Farey总数 9. Farey序列构造 10. Miller_Rabbin素数测试,Pollard_rho因式分解 五. 图论算法 1. 最小生成树(Kruscal算法) 2....

    Scratch编程-L3编程与算法18节课包含课件教案素材源码

    10-迷宫探险之鸡兔同笼11 - 11-迷宫探险之因数的个数12 - 12-迷宫探险之质数环13 - 13-迷宫探险之最大公约数14 - 14-迷宫探险之最小公倍数15 - 15-化龙池之余数定理16 - 16-化龙池之亲密数无pdf17- 17-最终之战之...

    算法导论(part1)

    本书是原书的第2版,在第1版的基础之上增加了一些新的内容,涉及算法的作用、概率分析和随机化算法、线性规划,以及对第1版中详尽的、几乎涉及到每一小节的修订。这些修订看似细微,实际上非常重要。书中引入了...

    求解“韩信点兵”问题的算法研究...程序设计

    这类问题和解法, 一般称它为孙子定理, 外国人称其为“ 中国余数定理” , 它是我国闻名 于世的古代数学定理。 这一工作不仅在数学历史上占有地位, 而且这类阔题的解法的原则在 现代数学中还在起着重要的作用 ] ...

    Competitive_Programming:用于竞争性编码竞赛的已实现数据结构和算法的便捷集合

    竞争性编程 ...欧几里得算法,GCD,LCM,mod逆,中国余数定理 和Pollard的方法 数-素数,Erasthosenes筛,Euler的求函数 快速傅立叶变换 快速傅立叶逆变换 -第二版 -最短路径。 具有自定义二进制堆的Dijk

    时—空欠采样下的频率和DOA联合估计算法

    针对时—空欠采样下入射信号的频率和波达方向(DOA)估计问题,提出基于谱校正和中国余数定理的联合估计算法。首先利用稀疏分布的传感器阵元构造非均匀线阵,然后对入射信号做多路并行欠采样;借助AM估计器,该算法仅耗费...

    论文研究-用于NANDFlash的长BCH编码快速算法.pdf

    算法利用分圆陪集和中国剩余定理,在确定生成多项式时,由每个最小多项式的根构造分圆陪集,避免了重复计算所有的根;采用等价多项式代替除法多项式,将计算的最小多项式和理想循环码的生成元加入分圆陪集,后续编码...

Global site tag (gtag.js) - Google Analytics