同余与模运算，求模运算和求余运算
温馨提示：这篇文章已超过522天没有更新，请注意相关的内容是否还可用！
同余模是数论中一个基本的运算规则；
????????????? ? 同余模：
a≡ b(mod d)
解释：a对d取模等于b对d取模
基本定律：
?????? 同余公式也有许多我们常见的定律,比如相等律,结合律,交换律,传递律….如下面的表示:
?????? 1)传递性 (a≡b(mod d),b≡c(mod d))→a≡c(mod d)
?????? 如果a≡x(mod d),b≡m(mod d),则
?????????? 2)a+b≡x+m （mod d）
?????????? 3)a-b≡x-m (mod d)
?????????? 4)a*b≡x*m (mod d )
?????????? 5)a/b≡x/m （mod d）
?????? 6）a≡b（mod d）则a-b整除d
?????? 7）a≡b（mod d）则a^n≡b^n(mod d)
????? 8)如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m）
模运算的基本规则:
???1. 加法 ??
(a + b)? mod? p = (a? mod? p + b? mod? p)? mod? p； ? ? ?
???
2.
?减法??(a – b)? mod? p = (a? mod? p – b? mod? p)? mod? p； ? ??
???
3.
?乘法??(a * b)? mod? p = (a? mod? p * b? mod? p)? mod? p；
? ?
4.
?幂运算 a^b? mod? p = ((a? mod? p)^b)? mod? p； //可使用快速幂取模?
???5.?
结合率 ((a+b)? mod? p + c)? mod? p = (a + (b+c)? mod? p)? mod? p；
???????????????????? ((a*b)? mod? p * c) mod? p = (a * (b*c)? mod? p)? mod? p；
? ?
6.
交换率 (a + b)? mod? p = (b+a)? mod? p；
???????????????????? (a * b)? mod? p = (b * a)? mod? p?；
? ?
7.
?分配率 ((a +b) mod? p * c)? mod? p = ((a * c)? mod? p + (b * c)? mod? p)? mod? p；
?
扩展取模运算：大数取模运算
例如：现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除10003之后的余数。
????????? ? 此时就要用到
加法和乘法的同余思想?
了
为什么呢？给你一个比较大的数例如 ? 12345
则
12345%mod =(((((((1*10%mod + 2)%mod）*10+3）%mod）*10+4）%mod)+5)%mod
;
则
x1x2x3x4x5….%mod =?
(((((((x1*10%mod + x2)%mod）*10+x3）%mod）活动：慈云数据爆款香港服务器，CTG+CN2高速带宽、快速稳定、平均延迟10+ms 速度快，免备案，每月仅需19元！！ 点击查看*10+x4）%mod)+x5)%mod ….
;
当然还有一种思路就是
幂运算取模和快速幂
的思想了：
x1x2x3x4x5….%mod = x1*10^(n-1)%mod + x2*10^(n-2)%mod?+ x3*10^(n-3)%mod?+ x4*10^(n-4)%mod?+ x5*10^(n-5)%mod ….;
n表示数的长度，^ 表示幂；????? ? 但是我写了过了案例，但没能过OJ,等我想通了再改！！！
代码：
#include #include #include #include using namespace std;const int maxn = 10000005;#define mod 10003char s[maxn];int main(){ int T; scanf(\”%d\”,&T); while(T–) { memset(s,0,sizeof(s)); scanf(\”%s\”,s); int ans = 0; int len = strlen(s); for(int i = 0; i
?
67674454
《同余与模运算，求模运算和求余运算》来自互联网同行内容，若有侵权，请联系我们删除！
