同余模定理

谁借莪１个温暖的怀抱￠ 2022-08-21 00:19 207阅读 0赞

# 同余模定理 #

定义：

• 所谓的同余，顾名思义，就是许多的数被一个数d去除，有相同的余数。d数学上的称谓为模。如a=6,b=1,d=5,则我们说a和b是模d同余的。因为他们都有相同的余数1。

• 　　数学上的记法为：

• 　　a≡ b(mod d)

• 　　可以看出当n<d的时候,所有的n都对d同商,比如时钟上的小时数,都小于12,所以小时数都是模12的同余.对于同余有三种说法都是等价的,分别为:

• 　　(1) a和b是模d同余的.

• 　　(2) 存在某个整数n,使得a=b+nd .

• 　　(3) d整除a-b.

• 　　可以通过换算得出上面三个说话都是正确而且是等价的.

定律：

• 同余公式也有许多我们常见的定律,比如相等律,结合律,交换律,传递律….如下面的表示:

• 　　1)a≡a(modd)

• 　　2)a≡b(modd)→b≡a(mod d)

• 　　3)(a≡b(modd),b≡c(mod d))→a≡c(mod d)

• 　　如果a≡x(modd),b≡m(mod d),则

• 　　4)a+b≡x+m （mod d）

• 　　5)a-b≡x-m(mod d)

• 　　6)a\*b≡x\*m(mod d )

•

应用：

• (a+b)%c=(a%c+b%c)%c;

• (a\*b)%c=(a%c\*b%c)%c;

• 对于大数的求余，联想到进制转换时的方法，得到

• 举例如下，设大数 m=1234,模n

• 就等于((((1\*10)%n+2%n)%n\*10%n+3%n)%n\*10%n+4%n)%n

大数求余的简单模板：

• \#include<stdio.h>//大数求余，其中n(除数）不是大数  
char a\[1000\];  
int main()  
int i,j,k,m,n;  
\{  
while(scanf("%s%d",a,&n)!=EOF)  
\{  
m=0;  
for(i=0;a\[i\]!='\\0';i++)  
m=((m\*10)%n+(a\[i\]-'0')%n)%n;  
printf("%d\\n",m);  
\}  
return 0;  
\}

poj2635

• **题目描述：**

• 给定一个大数K，K是两个大素数的乘积的值。(4<= K <= 10^100 )

• 再给定一个int内的数L (2 <=L <= 10^6 )

• 问这两个大素数中最小的一个是否小于L，如果小于则输出这个素数。

解题思路：

• 1、 Char格式读入K。把K转成千进制Kt，同时变为int型。

• 把数字往大进制转换能够加快运算效率。若用十进制则耗费很多时间，会TLE。

• 千进制的性质与十进制相似。

• 2、 高精度求模。

• 主要利用Kt数组和同余模定理。

• 例如要验证123是否被3整除，只需求模123%3

• 但当123是一个大数时，就不能直接求，只能通过同余模定理对大数“分块”间接求模

• (a+b)%c=(a%c+b%c)%c;

• (a\*b)%c=(a%c\*b%c)%c;

• 具体做法是：

• 先求1%3 = 1

• 再求（1\*10+2）%3 = 0

• 再求 （0\*10+3）% 3 = 1

• 那么就间接得到123%3=0，这是显然正确的

• 而且不难发现， （1\*10+2）\*10+3 = 123

• 这是在10进制下的做法，千进制也同理，\*10改为\*1000就可以了

发表评论取消回复

表情：

评论列表（有 0 条评论，207人围观）

还没有评论，来说两句吧...

相关阅读

相关同余模定理

同余模定理定义： • 所谓的同余，顾名思义，就是许多的数被一个数d去除，有相同的余数。d数学上的称谓为模。如a=6,b=1,d=5,则我们说a和b是模d同余的。因为他

谁借莪１个温暖的怀抱￠/ 2022年08月21日 00:19/ 0 赞/ 208 阅读

相关 LightOJ 1214 - Large Division【同余定理】

1214 - Large Division <table> <tbody> <tr> <td title="normal judge" style="col

我会带着你远行/ 2022年08月18日 02:35/ 0 赞/ 183 阅读

相关 pku 2115 C Looooops 同余定理

\include <stdio.h> long long mod(long long a,long long b) \{ return (a % b + b) % b; \}

- 日理万妓/ 2022年08月04日 15:53/ 0 赞/ 180 阅读

相关【light oj1078】Integer Divisibility（同余定理）

<table style="margin:0px; padding:0px"> <tbody style="margin:0px; padding:0px"> <tr

刺骨的言语ヽ痛彻心扉/ 2022年07月16日 02:41/ 0 赞/ 182 阅读

相关同余定理（求余数）

现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除10003之后的余数输入第一行有一个整数m(1<=m<=8),表示有m组测试数

左手的ㄟ右手/ 2022年07月15日 11:29/ 0 赞/ 224 阅读

相关同余定理（求余数）

现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除10003之后的余数输入第一行有一个整数m(1<=m<=8),表示有m组测试数

Bertha 。/ 2022年07月15日 11:29/ 0 赞/ 236 阅读

相关同余定理

同余运算及其基本性质 100除以7的余数是2，意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义：假如被除数是a，除数是b（假设它们均为正整数

悠悠/ 2022年06月17日 08:29/ 0 赞/ 244 阅读

相关【转载】--同余定理

同余运算及其基本性质 100除以7的余数是2，意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义：假如被除数是a，除数是b（假设它们均

矫情吗；*/ 2022年06月10日 12:28/ 0 赞/ 970 阅读

相关 Integer Divisibility LightOJ - 1078——同余定理+逆元（大数取模）

If an integer is not divisible by 2 or 5, some multiple of that number in decimal notati

缺乏、安全感/ 2022年05月18日 00:05/ 0 赞/ 190 阅读

相关【算法】同余定理及快速幂求模

文章目录定义及其性质大数的高精度对单精度取模快速幂取模(次方求模) 定义及其

港控/mmm°/ 2022年04月01日 10:00/ 0 赞/ 388 阅读