欧拉函数

洛谷 P3747 相逢是问候 题解【树状数组】【欧拉定理】【快速幂】【平衡树】

     一道充分考察了扩展欧拉定理的题目,并且细节要求比较多。   题目描述 Informatik verbindet dich und mich. 信息将你我连结。   B 君希望以维护一个长度为\(n\)的数组,这个数组...

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

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