同余与模运算

2019-04-13 12:00发布

站内文章 / 模拟电子
10154 0 1559
1、基本运算：///溢出情况，b为正整数 加法：(a+b) mod n = ((a mod n)+(b mod n))mod n 减法：(a-b) mod n = ((a mod n)-(b mod n)+n) mod n 乘法：ab mod n = (a mod n)(b mod n) mod n 
2、大整数取模： char st[1000]; int m; scanf("%s%d",st,&m); int len =strlen(st); int ans=0; for(int i=0;i
3、幂取模：a^n mod m  采用分治法解决
4、模线性方程组（同余方程）：ax = b(mod n) 即  ax-b = ny 可用扩展欧几里德算法解决 特殊情况：当b=1时，称解为a关于模n的逆，当且仅当a与n的gcd（最大公约数为1）时存在唯一解


热门文章