二次剩余 原根
改题，然后发现需要填填坑。
其实学起来也没有那么难。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Cauphenuny's Blog！
相关推荐
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 互质，则...
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...
评论