zcmimi's blog

arrow_back数论共123篇文章

avatar
zcmimi
2020-07-05 15:56:00

阶:

定义:

m>1\gcd(a,m)=1,那么使得a^r \equiv 1 \pmod m成立的最小的正整数r称为a对模m的阶,记为\delta_m(a),或ord_m a

定理:

  1. m>1gcd(a,m)=1,满足$a^n\
avatar
zcmimi
2020-07-04 21:50:00

刚入门数论的OIer有可能被数论符号整的一脸懵逼,一下特地整理了常用的数论符号及其含义

  1. 组合数: n\choose mC_n^m

  2. 莫比乌斯函数: \mu

  3. 欧拉函数: \varphi\varPhi

  4. 阶: a关于模m的阶,记

avatar
zcmimi
2020-07-01 13:58:00

定义

n个元素中取出m个的方案数,记为n\choose mC_n^m

{n\choose m}=\frac{n!}{m!(n-m)!}

帕斯卡法则

{n-1\choose m}+{n-1\choose m-1}={n\choose m}

avatar
zcmimi
2020-06-25

推荐:

定义

生成函数又称母函数

设序列aa_0,a_1,a_2,\dots

avatar
zcmimi
2020-06-22 21:09:00

https://www.51nod.com/Challenge/Problem.html#problemId=1822

定义

$$ \begin{cases} B0=1\~\ \displaystyle \sum\limits{i=0}^n {n+1\choose i}B_i=0,

avatar
zcmimi
2020-06-09 16:22:00

DZY Loves Math

题意:

对于正整数n,定义f(n)n所含质因子的最大幂指数

例如f(1960)=f(2^3\cdot 5^1\cdot 7^2)=3,f(10007)=1,f(1)=0

给定正整数a,b,求$\sum\limits_{i=1}^a\s

avatar
zcmimi
2020-03-15 17:10:00

前置知识: 狄利克雷卷积

求积性函数f的前缀和:

S(n)=\sum_{i=1}^nf(i)

大部分题目都是可以线性筛的,可是某些丧心病狂的出题人会: n\le 10^{12}!

这时候需要用杜教筛了

我们构造另

avatar
zcmimi
2020-03-14 22:46:00

数论函数

  1. 加法

    逐项相加

    (f+g)(x)=f(x)+g(x)

  2. 数乘

    (xf)(n)=x\cdot f(n)

定义

两个数论函数的狄利克雷卷积∗

t=f*g等价于

$$t(n)=\sum_{i|n}f(i)

avatar
zcmimi
2020-03-12 20:40:00

该好好复习(总结)一下莫比乌斯函数了呢\mathcal{>_\omega<}

定义

$$ \mu (i)= \begin{cases} 1,i=1 \ (-1)^k,i=p_1\times p_2\times \dots \times p_k \ 0,rest \end{cases

avatar
zcmimi
2020-03-07 15:50:00

扩展中国剩余定理

给定方程组:

$$ \begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \ x\equiv a_2\ ({\rm mod}\ m_2) \ ... \ x \equiv a_n\ ({\rm mod}\ m_n) \end{cas

2/13
Search
search