本蒟蒻第一次讲课，由于比较匆忙所以没有及时准备课件，在此表示抱歉… 听说他们讲课都是啥都没有 在那儿唠嗑 20 20 20分钟然后问:有没有不会的 不会的自己学 就完事了？？ 2333 2333 2333真是负责

这是一篇数论 0 0 0零起点到负无穷，从入门到入土的博客 请大家做好心理准备

听说 C C C层要讲数论? 哈 作为前数学竞赛生的我当然要抢着讲了 于是跟 p j t pjt pjt大哥蹭了一下 本着放松随便讲一讲的心态 我问了我们这边的 l y s s lyss lyss小宝宝

但是 p j t pjt pjt去自由啊…那就我自己写吧…

t i p s : tips: tips:现在要讲的基本涉及的都是整数 所用的字母除声明外也都表示整数

1.设 a a a、 b b b是给定的数 ， b ≠ 0 ，b\neq0 ，b=0。若存在整数 c ， c， c，使得 a = b c ， a=bc， a=bc，则称 b b b整除 a ， a， a，记作 b ∣ a ， b\mid a， b∣a，反之 , , ,则称 b b b不能整除 a ， a， a，记作 b ∤ a b\nmid a b∤a。 2.一些性质:

a. 若 a ∣ b a|b a∣b，且 b ∣ c b|c b∣c，则 a ∣ c a|c a∣c。 b. 若 b ∣ a b|a b∣a，且 b ∣ c b|c b∣c，则 b ∣ ( a ± c ) b|(a\pm c) b∣(a±c) c.若 c ∣ a c|a c∣a，且 c ∣ b c|b c∣b，则对于任意整数m、n，有 c ∣ ( m a + n b ) c|(ma+nb) c∣(ma+nb)。

         \,\,\,\,\,\,\,\, 对于一个正整数，如果它有且仅有1和它自己两个约数，那么我们称这个数为素数。如果有两个以上的约数，那么我们称这个数为合数。注意:1既不是素数也不是合数

先植入一个没什么用的定理，它叫素数定理: 小于x的素数的个数近似等于x/ln(x)…

现在我们想想如何求素数

1.考虑暴力枚举

如果 2 − n 2 -\sqrt{n} 2−n ​每个数都不是 n n n的因子，那么 n n n就是质数了。 复杂度 O ( n ) O(\sqrt{n}) O(n ​)

那么我们来看一道题： 求 1 − n 1-n 1−n内的素数。 n < = 1000000 n prime[++cnt]=i; for(int j=1;j*i vis[i*prime[j]]=true; if(i%prime[j]==0)break; } }

在筛到每个数时 我们把小于它的最小质数的所有质数倍数的数都筛掉 这样就能保证每个数是被它自己最小的质因子筛掉

g c d gcd gcd是啥？ l c m lcm lcm是啥？某党？

g c d gcd gcd指的是 g r e a t e s t    c o m m o n    d i v i s o r greatest\,\,common\,\, divisor greatestcommondivisor就是最大公约数。 l c m lcm lcm指的是 L e a s t    C o m m o n    M u l t i p l e ， Least\,\,Common\,\,Multiple， LeastCommonMultiple，即最小公倍数。

最大公约数是数论中一个重要的概念

设 a a a、 b b b不全为零 , , ,同时整除 a a a、 b b b的整数称为他们的公约数 ， ， ，显然 a a a、 b b b的公约数只有有限多个 ， ， ，我们将其中最大的一个称为 a a a、 b b b的最大公约数表示 ， ， ，用符号 ( a , b ) (a,b) (a,b)表示。显然 ， ， ，最大公约数是一个正整数。 当 ( a , b ) = 1 (a,b)=1 (a,b)=1时 ， ， ，我们称 a a a与 b b b互质 ( ( (互素 ) ， )， )，这种情形特别重要。

那么问题来了 我们怎么求最大公约数呢？ 通常用辗转相除法来写 我的个人喜好是用递归 辗转相除法是不都会…? 算了算了 好好讲讲吧 我们可以很显然地理解这个等式:

g c d ( a , b ) = g c d ( a − b , b ) gcd(a,b)=gcd(a-b,b) gcd(a,b)=gcd(a−b,b)

但是呢 这么一次一次减太慢了 所以我们一次能减多少就减多少 就相当于直接除 这就是简述版的辗转相除

我不会告诉你们algorithm库里有可以直接用的__gcd 辗转相除在后面个的扩展 g c d gcd gcd中还是很有用的 上两个题吧

luoguP1372 简述版题意:给你个 n n n和 k k k 求 n n n个数中取 k k k个的最大公约数最大

S o l u t i o n : Solution: Solution:设这 k k k个数的最大公约数为 g c d gcd gcd 则第 k k k个数最小为 k × g c d k×gcd k×gcd 所以 k × g c d ≤ n k×gcd\leq n k×gcd≤n 那么 g c d ≤ n k gcd\leq\frac{n}{k} gcd≤kn​ 显然最大的 g c d = ⌊ n k ⌋ gcd=\lfloor\frac{n}{k}\rfloor gcd=⌊kn​⌋

时间复杂度: O ( l o g n ) O(log_n) O(logn​) 10.23     23 : 12 10.23\,\,\,23:12 10.2323:12今天先写到这儿 明天应该讲不到这儿

引题:给定 a 、 b 、 c ， a、b、c， a、b、c，求使得 a x + b y = c ax+by= c ax+by=c成立的最小正整数解 x 、 y ， x、y， x、y，如果无解则输出 l y s w a n lyswan lyswan 讲真的 我是从这个题开始认识到信息真的是一门竞赛…

S o l u t i o n : Solution: Solution: 1. 1. 1.首先考虑是否有解:当 g c d ( a , b ) ∣ c gcd(a,b)\mid c gcd(a,b)∣c时方程才有解 2. 2. 2.所以我们先不管 c c c到底是 g c d ( a , b ) gcd(a,b) gcd(a,b)的几倍 直接给 我们考虑如何搞这个方程: 首先看这个方程: b x + ( a % b ) y = c bx+(a\%b)y= c bx+(a%b)y=c这样以此类推 最后会得到 g c d ( a , b ) x = c gcd(a,b)x= c gcd(a,b)x=c此时 x = 1 x=1 x=1 对于 a ′ = b , b ′ = a % b a' = b, b' = a\% b a′=b,b′=a%b而言，我们求得 x , y x, y x,y使得 a ′ x + b ′ y = g c d ( a ′ , b ′ ) ， a'x + b'y = gcd(a', b')， a′x+b′y=gcd(a′,b′)， 由于 b ′ = a % b = a − ⌊ a b ⌋ × b b' = a \% b = a - \lfloor\frac{a}{b}\rfloor ×b b′=a%b=a−⌊ba​⌋×b 所以可以推得 a y + b ( x − ⌊ a b ⌋ × y ) = g c d ( a , b ) ay +b(x - \lfloor\frac{a}{b}\rfloor ×y) = gcd(a, b) ay+b(x−⌊ba​⌋×y)=gcd(a,b) 即一组通解为 x = y , y = x − ⌊ a b ⌋ × y x=y,y=x - \lfloor\frac{a}{b}\rfloor ×y x=y,y=x−⌊ba​⌋×y

问题来了 我们怎么用代码实现呢? 注意到我们方程的变形用的是 g c d gcd gcd函数辗转相除，方程的通解是一步一步递归才能得到 所以用递归版的欧几里得顺便求得。 这个就叫扩展欧几里得 上代码:

最后的 x , y x,y x,y就是解 不过出来可能会是一个负数 求最小正整数解还要再加上一个 m o d mod mod

这个东西其实真的很有用的 我们看一道题 N O I P 2012 NOIP2012 NOIP2012同余方程 题意:求关于 x x x的同余方程 a x ≡ 1 ( m o d b ) a x \equiv 1 \pmod {b} ax≡1(modb)的最小正整数解。

S o l u t i o n : Solution: Solution:转化为 a x + b y = 1 ax+by=1 ax+by=1 就变成了扩展欧几里得… 代码:

仔细体会其实不难 上例题: 题面找不到了 大哥们我错了 题意:给定 n n n,求 1 ≤ x , y ≤ n 1\leq x,y\leq n 1≤x,y≤n且 g c d ( x , y ) = 1 gcd(x,y)=1 gcd(x,y)=1的数对个数 这就用到我们前面讲的 某些问题的 g c d = 1 gcd=1 gcd=1可以转化为欧拉函数 用式子写出来就是: ∑ i = 1 n ∑ j = 1 n ( g c d ( i , j ) = 1 ) \sum_{i=1}^n \sum_{j=1}^n (gcd(i,j)=1) ∑i=1n​∑j=1n​(gcd(i,j)=1) = ∑ i = 1 n φ ( i ) =\sum_{i=1}^nφ(i) =∑i=1n​φ(i) 所以只需要求出欧拉函数的前缀和即可

终于来到最有用的地方了…

什么是逆元? 对于一个数 x ， x， x，它在模 p p p意义下的逆元 a a a，满足 a x ≡ 1 ( m o d p ) ， ax\equiv 1\pmod p， ax≡1(modp)， 这东西很有用 可以说没有逆元数论少了灵魂 看这个题:给定 n , m , p n,m,p n,m,p求 n m m o d    p \frac{n}{m}mod\,\,p mn​modp 如果你没学逆元 你肯定懵逼: w o c ? ? woc?? woc??分数还能取模？ 这就是逆元的妙处 S o l u t i o n : Solution: Solution:求出 m m m在模 p p p意义下的逆元 a a a，答案为 n a % p na\%p na%p。 那么这么好用的一个东西 我们怎么求呢??? 求逆元的方法

1. 1. 1. e x g c d exgcd exgcd 逆元满足什么条件? a x ≡ 1 ( m o d p ) ax\equiv 1\pmod p ax≡1(modp)?同余方程啊！ e x g c d exgcd exgcd显然可行啊。 性能分析:

2. 2. 2.快速幂 快速幂怎么求逆元? 那首先你需要了解一个定理—费马小定理:

若 p p p为素数，那么 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv 1\pmod p ap−1≡1(modp)

这个是怎么来的呢? 欧拉定理的推论 欧拉定理(有时也叫作费马小定理的一般式):

a φ ( p ) ≡ 1 ( m o d p ) a^{φ(p)}\equiv 1\pmod p aφ(p)≡1(modp)

那欧拉定理怎么来的呢?有兴趣自己查查(其实是来不及了！！ 接着说 因为 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv 1\pmod p ap−1≡1(modp)，所以 a p − 2 a^{p-2} ap−2就是 a a a的逆元 性能分析:

3. 3. 3. 线性求逆元 放心放心 这次线性没有筛 不用害怕 原理: p p p是模数,我们现在要求的是 i i i的逆元 将 p p p写成 p = k ∗ i + r p=k∗i+r p=k∗i+r其中 0 < r < i 0 if(b&1)(ret*=a)%=mod; (a*=a)%=mod,b>>=1; } return ret; } ll n,m; ll getint(){ char chr=getchar();ll x=0; while(chr'9')chr=getchar(); while(chr>='0'&&chr n=getint(),m=getint(); if(m==0)return printf("Angry!"),0; printf("%lld\n",n*quickpow(m,mod-2)%mod); }

板子题 题意：给定 n , p n,p n,p求 1 − n 1-n 1−n中所有整数在模 p p p意义下的乘法逆元。 S o l u t i o n : Solution: Solution:没有 S o l u t i o n Solution Solution，线性求逆元直接过