数论基础

本文来自我的选修课-课堂纪要

一、课堂语音识别

数论是ICPC中头疼的，数论现在在比赛的时候用得越来越多。2020.09月记录
数论的内容比较多，不可能通过一次课讲清楚，这次讲数论，因为有可能会考试
我们讲解2欧——欧拉和欧几里得『这2欧，搞数论的基本上离不开』
欧拉函数基础知识
数论的题在比赛中会大量的遇到，几乎，没有哪次比赛中没有一道数论题的

二、欧拉函数

（用得非常多）

1.欧拉函数

$Euler(n)=n*(1-\frac{1}{p1})*(1-\frac{1}{p2})*...*(1-\frac{1}{pn})$

其中：

p₁,p₂,...p_n 是n的所有素数因子
$Euler(n) :所有小于等于n的且与n互素的数的个数$

欧拉函数用之前是需要获得素数表的。

以欧拉命名的很多，欧拉函数，欧拉定理啥的
我们这里用的欧拉是用得比较多的一个。

Euler（欧拉）函数

学过离散数学的都知道。
欧拉函数很出名，不知道都不好意思说是大学生？高中生？
PS：吐槽：我咋不晓得...

2.例题-杭电OJ-1286

HDU-1286-找新朋友-传送门

三、扩展欧几里得

（Euclid）