12
编程数学
专题知识12 个分类 · 64 个知识点
面向信息学竞赛的数论知识体系,涵盖整除同余、素数、数论函数、组合计数等核心数学内容
简单 1中等 3困难 60
01
整除与同余基础
5 个知识点整除的概念与性质、带余除法、同余概念、模运算规则
02
最大公约数与欧几里得算法
6 个知识点GCD概念、辗转相除法、扩展欧几里得算法、二元一次不定方程、LCM
03
素数与素数筛法
6 个知识点素数判定、埃氏筛、线性筛、区间筛、素数分布
04
质因数分解
5 个知识点算术基本定理、试除法分解、Miller-Rabin素性测试、Pollard Rho因子分解
05
模逆元
5 个知识点模逆元概念、费马小定理求逆元、扩展欧几里得求逆元、线性预处理逆元
06
欧拉函数与欧拉定理
5 个知识点欧拉函数定义与性质、欧拉定理、扩展欧拉定理(降幂公式)
07
同余方程与中国剩余定理
5 个知识点一元线性同余方程、中国剩余定理(CRT)、扩展中国剩余定理(ExCRT)
08
积性函数与莫比乌斯反演
6 个知识点积性函数、莫比乌斯函数、狄利克雷卷积、莫比乌斯反演、杜教筛
09
组合数论
6 个知识点加法乘法原理、排列组合、二项式定理、卢卡斯定理、容斥原理、卡特兰数
10
快速幂与矩阵快速幂
6 个知识点快速幂、快速幂取模、矩阵运算、矩阵快速幂、矩阵求斐波那契数列
11
高斯消元与线性基
4 个知识点高斯消元解方程组、异或方程组、线性基构造、线性基求异或极值
12
FFT与NTT
5 个知识点多项式运算、复数与单位根、FFT快速傅里叶变换、NTT数论变换