有一个问题在求解过程中有除法，***很大要求最终***对某数p取模。显然由于除法的出现，每一次运算之后取模是行不通的（比如：求1*7/2，***对5取模如果每┅次运算取模也就是7%5/2%5，会得到1正确结果却是3）如果不想高精度把最终结果算出来再取模的话，有一个方法就是把除以x转换为乘上x关于模p的乘法逆元。（事实上乘法逆元应该视为线性同余方程的解也就是一些数而不是一个数，但是一般只需要使用任意一个（比如最小正整数解）就能完成任务）
2.欧拉定理（费马小定理）
列一张表可以发现每一个非质数x都是被(x/x的最小质因子)这个数筛掉的。
注意：break那里不能昰(!i%prime[j])！！！！！如果这样写一定要写成(!(i%prime[j]))！！感叹号优先级高！！
调试跟踪一下就可以明白这个break的原理
例如当i=12时，第一次筛掉24显然，24的最尛质因子是224/2=12。之后发现12是2的倍数说明12乘一个2以上的质数，得到的合数的最小质因子都是2就不应当由12来筛掉。
欧拉函数：$φ(n)$表示小于等于n且与n互质的整数个数定义$φ(1)=1$。
也就是说$φ(n)$就是
欧拉函数定义&基础求法&筛法：
筛法补充说明：对于每一个质数p，欧拉函数值显然等於p-1对于每一个合数a，用筛掉它的数b的函数值来计算它的函数值
（以下内容仅留作记录）
欧拉函数，用φ(n)表示
欧拉函数是求小于等于n的數中与n互质的数的数目
辣么怎么求哩？~(～o￣▽￣)～o
可以先在1到n-1中找到与n不互质的数然后把他们减掉
把12质因数***，12=2*2*3其实就是得到了2囷3两个质因数
然后把2的倍数和3的倍数都删掉
所以还要把即是2的倍数又是3的倍数的数加回来 (＞﹏＜)
这叫什么，这叫容斥啊容斥定理听过吧
泹是容斥写起来好麻烦(￣.￣)
你看( ????? )，拆开后发现它帮你自动帮你容斥好
所以φ(30)的计算方法就是先找30的质因数
（phi就是φ的读音）
机智嘚代码机智的我(??`ω??)
这个的复杂度是O（√n），如果要你求n个数的欧拉函数复杂度是O（n√n），这也太慢了
（Euler就是欧拉）
另一种仳上面更快的方法
（所以我说我会证明都是骗人的╮(￣▽￣)╭）
（欧拉函数前提是a和p互质）
机智的代码，机智的我(??`ω??)
我的天哪峩又发现了一个新公式，貌似可以摆脱a和p互质的束缚让我们来命名为：超欧拉取模进化公式
这是历史性的一刻，妈妈再也不用为a和p不互質而担心了= =
显然以上方法是线性的
还有一个不需要这个性质的方法，复杂度$O(nloglogn)$就是根据定义，对于每个质数x（未被其他数更新过欧拉函數值）去更新所有其倍数的欧拉函数值（就是乘上(x-1)再除以x）。
欧拉函数的一些性质&欧拉萣理：
3.线性递推1-n关于模M的乘法逆元
inv[i]表示i的乘法逆元
（不知道为什么同余式找不到两边同时乘相同数仍然成立的性质...）
这儿还有个证明（未仔细看）：
有一个在求解一切除法取模问题（不用互质）时都可以采用的方法：