ACM取模总结

2019-04-14 20:35发布

站内文章 / 模拟电子
13960 0 1590
ACM题经常会遇到各种各样的取模运算。 于是网上搜了一下，在这把能用的东西总结一下，方便以后使用。 文章参考的百度文库中一个朋友的文章，本来想吧地址粘贴过来，今天再去找找不到了。日后见到再粘贴吧。 繁琐的东西咱就不说了。只说一些能够用的到的。 取模： 先说一点，就是取模运算n%p的结果与p的符号无关，由n决定。 例如：7%4=3,-7%4=-3,7%-4=3，-7%-4=-3； 基本的运算： (a+b)%p=(a%p+b%p)%p (a-b)%p=(a%p-b%p)%p (a*b)%p=(a%p*b%p)%p (a^b)%p=((a%p)^b)%p 前边三个很简单一看就知道，后面这个用的很多，因为有这样一类题。下面说。 重要定理： a≡b(%p) 对任意的c都有（a+c)≡(b+c)(%p); 两数想成同样符合 a≡b(%p) 对任意的c都有  (ac）≡（bc)(%p); a≡b(%p),c≡d(%p)则 （a+c)≡(b+d)(%p) (a-c)≡(b-d)(%p) (ac)≡(bd)(%p) (a/c)≡(b/d)(%p) 我写这篇文章的主要目的在这： 应用： 1，判断奇偶数 x%2=1 奇数 x%2=0 偶数。 2，判断素数 试除法 查余数是否为零 表示整除。 3，最大公约数，最小公倍数 t=a%b； a=b;b=t;循环； 4，模幂运算  例如求3333^5555 的个位数几 运用上面基本运算里的第四个得到3333^55555=>3^5555(%10）然后找规就行了。 5，孙子问题（中国剩余定理） 这个我就不多说了大家看一下维基百科里面讲的很详细：zh.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86  在这里我说一下他的程序实现： 我们这里用维基百科里的变量，看完维基百科后总体的意思就能把握实现起来我认为只有一点不好实现，那就是在求ai的时候 这里用了weile（）循环 ，这里我们来如果不能除得余数为1，就加上一个Mi继续除直到除到为1； unsigned int ResidueTheorem(const unsigned int devisor[], const unsigned int remainder[], int length)     {     unsigned int product = 1; //所有除数之乘积    for (int i=0; i
  代码可能有点乱，但是主要是为了看懂意思。
6，凯撒密码  这个也是比较简单 (a+x)%26  (b-x)%26 就是这个样子
好了！找到了参考的文章，仅有的一段代码也来自这篇文章，但是文章中有小的地方有失误，大家可以看看，毕竟比我写的好. wenku.baidu.com/view/2d2dc01dfad6195f312ba6d8.html
好了!  感谢自己坚持！

热门文章