同余

数学小知识点【学习笔记】 upd on 2018.11.7

  一、线性求逆元 1.1~n的逆元     单独一个数\(\mod p\)的逆元是可以用费马小定理(\(p\)为质数)或exgcd在\(O(\log p)\)的复杂度内求的。但是如果要求\(1\sim n\)的逆元,其实用不到\(O(n\log n)\)。正如...

洛谷 P3868 [TJOI2009]猜数字 题解【同余】【逆元】【中国剩余定理】【快速乘】

      假装中国剩余定理入了门。。。   题目描述 现有两组数字,每组k个,第一组中的数字分别为:a1,a2,...,ak表示,第二组中的数字分别用b1,b2,...,bk表示。其中第二组中的数字是两...