Tag: number theory | Yuhang's Blog

Tag : number theory

扩展中国剩余定理

考虑$\mathbb{Z}$上的线性同余方程组 $x \equiv a_i \bmod n_i$, 其中$i = 1, .., r$. 则该方程组有解, 当且仅当对于任意$i\not= j$, 都有$a_i \equiv a_j \bmod \text{gcd} (n_i, n_j)$. Read more

2024-11-04 Mathematics

数论分块

引入考察定义在正整数集上的函数$f(x)=\left\... Read more

2021-03-01 CodingMathematics

质数的线性筛法和积性函数值的计算

质数的线性筛法比埃氏筛法复杂度更优，且可以被用来求积性函数的函数值。本文给出了相应的数学背景和代码实现，给出了三个常用积性函数（欧拉函数、莫比乌斯函数和除数函数）的线性筛法求法。 Read more

2021-02-28 CodingMathematics

莫比乌斯反演入门

莫比乌斯反演入门：积性函数、Dirichlet 卷积、反演和一道例题。 Read more

2021-02-27 CodingMathematics

题解 CF55D ：数位DP+数论

这题做了半天。美丽的数的定义是“可以被自己的所有非零数位整除的数”。做数位DP，想的就是每个状态需要什么参量来表示。注意到这个定义的限制并不在选取每个数位的时候，而是... Read more

2020-12-16 Coding