同模余定理
标签: 机试攻略 - 高分篇
学习人数: 34.8k


高清播放
赞赏支持

同余模是一个大家容易忽视的点,它一般不会单独作为考点出现,而是在其他类型的题目中作为一个常识的形式出现。

 

定义

所谓的同余,顾名思义,就是许多的数被一个数 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(mod d) 
2) a≡b(mod d)→b≡a(mod d) 
3) (a≡b(mod d),b≡c(mod d))→a≡c(mod d)

如果a≡x(mod d),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; 
(a*b)%c=(a%c*b%c)%c;

 

求S(n)
题目描述:
S(n)=n^5
求S(n)除以3的余数
输入描述:
每行输入一个整数n,(0 < n < 1000000) 
处理到文件结束
输出描述:
输出S(n)%3的结果并换行
输入样例#:
1
2
输出样例#:
1
2
题目来源:
DreamJudge 1500

题目解析:通过分析我们可以发现,n虽然不大,但是n^5却超过long long的范围,所幸的是题目只要我们对答案%3,这时候我们就可以运用同余模定理。
S(n)%3=(n^5)%3=(n*n*n*n*n)%3=((n%3)*(n%3)*(n%3)*(n%3)*(n%3))%3

 

参考代码

#include<stdio.h>  
#include<iostream>  
using namespace std;  
  
int main() {  
    long long int n;  
    while(~scanf("%lld",&n)) {  
        long long int s=n;  
        // 同余模定理:  
        for(int i=1;i<5;i...
登录查看完整内容


课后作业

掌握同模余定理


登录后开始许愿

暂无评论,来抢沙发