二次剩余 原根
改题，然后发现需要填填坑。
其实学起来也没有那么难。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Cauphenuny's Blog！
相关推荐
2020-11-01
BSGS
求解满足 ax≡b(modp)a^x\equiv b\pmod pax≡b(modp) 的最小 xxx （ ppp 是质数） 分块？设分块大小为 ttt 考虑 i∈[0,⌈nt⌉],j∈[1,t]i\in[0,\left\lceil\dfrac{n}{t}\right\rceil],j\in[1,t]i∈[0,⌈tn⌉],j∈[1,t] 则 axa^xax 可以表示成 ait−ja^{it-j}ait−j ait−j≡b(modp)a^{it-j}\equiv b\pmod p ait−j≡b(modp) 转换一下 ait≡baj(modp)a^{it}\equiv ba^j\pmod p ait≡baj(modp) 预处理出所有的 bajba^jbaj 存到一个 map / unordered_map 中，在枚举 i in range[1, n/t] 判断 aita^{it}ait 是否和某个元素 bajba^jbaj 相等，答案即为 it−jit-jit−j 复杂度...
2020-10-25
欧拉函数习题
acwing202. 最幸运的数字 P2398 GCD SUM 给定 nnn ，求 ∑i=1n∑j=1ngcd(i,j)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd(i,j)i=1∑nj=1∑ngcd(i,j) 数据范围：n≤105n\leq10^5n≤105 不需要反演也能做！ 挨个枚举 i,ji,ji,j 复杂度太高，考虑枚举 gcd(i,j)\gcd(i,j)gcd(i,j) 的值。 对于所有 gcd(x,y)=1\gcd(x,y)=1gcd(x,y)=1，有 gcd(xk,yk)=k(xk≤n,yk≤n)\gcd(xk,yk)=k\quad(xk\leq n,yk\le n)gcd(xk,yk)=k(xk≤n,yk≤n) 所以 gcd(i,j)=k\gcd(i,j)=kgcd(i,j)=k 的 i,ji,ji,j 的个数为：2∑i=1⌊n/k⌋φ(i)−12\sum\limits_{i=1}^{\lfloor...
2020-10-25
欧拉函数结论
∀n>1\forall n>1∀n>1 ，111 ~ nnn中与 nnn 互质的数的和为 12n×φ(n)\dfrac{1}{2}n\times\varphi(n)21n×φ(n) 证明：gcd(n,x)=gcd(n,n−x)gcd(n,x)=gcd(n,n-x)gcd(n,x)=gcd(n,n−x)，所以与 nnn 互质的数成对出现，平均数为 n/2n/2n/2 。 若 p 为素数， φ(pk)=pk(1−1p)=pk−1(p−1)\varphi(p^k)=p^k(1-\dfrac{1}{p})=p^{k-1}(p-1)φ(pk)=pk(1−p1)=pk−1(p−1) φ(n)=n(1−1p1)(1−1p2)…(1−1pk)\varphi(n)=n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})\ldots(1-\dfrac{1}{p_k})φ(n)=n(1−p11)(1−p21)…(1−pk1) 证明：容斥 若 aaa， bbb 互质，则...
评论