🔖 math数论既约剩余系欧拉函数

欧拉函数

今天学习一些欧拉函数及其相关的性质和定理：

  • 欧拉函数 φ(N)：

    φ(N) 表示 {1,2,3,⋯,N−1} 中与 N 互质的数的个数。

  • 数论欧拉定理：

    当 a 和 N 互质时，有：aφ(N)≡1modN

🔖 math数论素数欧拉函数线性筛

筛素数的算法

朴素筛法

朴素的筛素数算法的流程是这样的：

  1. i 没有被标记，i 是素数；用 i 去标记所有的 i,2i,⋯,⌊Ni⌋×i

  2. i 被标记，i 不是素数

因为每个数至少被所有它的素因子各自标记一次，而每个数的素因子个数是不超过

🔖 math数论扩展欧几里得算法中国剩余定理Baby Step Gaint Step

扩展欧几里得算法

问题描述

已知 a,b 为常整数，求方程 ax+by=gcd(a,b) 的一对整数解?

问题简析

令 {A=amodbB=b，构造方程

🔖 acm算法树链剖分

算法简介

树链剖分是将树上的节点映射到一段连续的区间中，使得树上任意一条路径能用不超过 O(log⁡N)  段连续区间表示。这样，利用线段树就可以在 O(log2⁡N) 的时间复杂度对树上任意路径上的节点进行进行维护和查询了。

算法原理

  • siz(u): 以 u 为根的子树的节点数

🔖 acm数据结构树链剖分线段树解题报告

题意简述

一棵 N 个节点的树，以 1 为根。树上的每个节点有两个权值：vi，ti。初始时均为 0。有 Q 次操作，每次操作为下列之一：

  • 1 u d: 对 u 到根上所有点执行 vi+=d
  • 2 u d: 对 u 到根上所有点执行 ti+=vi×d

🔖 math组合数学

预备知识

  • 组合数

    (nm)=C(n,m)={n!m! (n−m)!,n⩾m0,n<m

  • 第二类斯特林数

    S(n,m)=mS(n−1,m)+S(n−1,m−1)=1m!∑k=0m(−1)k(mk)(m−k)n其中， n>1,m⩾1。
© 2017-2025 光和尘有花满渚、有酒盈瓯