简单的定义:对于m(m>1),在 [1m] 区间中所有与 m 互素的数可以构成一个缩系.
缩系性质 1,缩系中必定每个元素都有自己唯一的逆元,并且每个元素的逆元不与其他元素的重复 (一一对应的关系).
逆元的定义:
由缩系性质1:定理1成立.
所以,如果 p 为质数,我们就可以放心地求 p 以内所有数的逆元.
由于逆元的定义:xa=1(mod p)
所以我们可以用扩展欧几里德算法求出使 ax=1 的 x,xa+yp=1
cout<<inv<<endl;
证明:这里需要应用缩系的性质2,3.
如果这个方法随时可以用的话我们还要那么多求逆元的方法干什么.
你不觉得·随时除会除出小数吗? 所以也许是装逼用的吧.比如你可以写这样的代码:
大佬大佬,问一下我在别的大佬的博客里看到了这个:
请问这个是在哪些条件下可以用的呢?