玖的数学&算法录

致谢

首先我能够有这一个博客，与我的朋友remy有很大的关系，这里特别感谢他这几天一直来帮我debug。

友链喵（熟人直接给会补上的捏）

0x3喵：梦安咖啡馆

该博客会以数学与算法为主，其中数学以分析方向为主，其他方向我不擅长，算法里面的数学内容大概率会更新，但不会有太多。

特别提醒：该日志会不断更新（？

2023 寒假

牛客寒假训练营好玩，经常写一会就睡着了。

2023寒假训练营第一场

2023寒假训练营第二场

2023寒假训练营第三场

2023寒假训练营第四场

2023寒假训练营第五场

2023寒假训练营第六场

2022 暑假

数学：

数学分析每日一题

2022牛客多校：（太坐牢了，不想补了）

2022牛客多校第一场

2022牛客多校第二场

2022牛客多校第三场

2022牛客多校第四场

2022牛客多校第五场

2022牛客多校第六场

2022牛客多校第七场

2022牛客多校第八场

2022牛客多校第九场

2022牛客多校第十场

标签

数学分析：

一个常见无穷积分的证明

一道非数学系竞赛题的推广

数列极限的几种计算方法

算法笔记：

算法笔记（00）：STL专题

算法笔记（01）：排序中的算法

算法笔记（02）：背包问题

算法笔记（03）：树状数组与线段树

算法笔记（04）：基础dp

算法笔记（05）：并查集

Codeforces讲解:

Educational Codeforces Round 124 (Rated for Div. 2)

Educational Codeforces Round 131 (Rated for Div.2)

受牛客多校队友影响，也开始了Codeforces补千题的计划（不准备了，好累，随缘更新）

Codeforces补题

代码模板

对于该ACM代码模板，不保证里面的代码能考虑到所有的情况，因此如果借用模板没通过，多读读题。

链接

板子

2022目标

Codeforces rank 蓝名门槛至中间 (多练)

以及EDG夺冠的Flag（希望毕业前能完成）：

Stein 《复分析》第四版

啃裴砖、樊砖

公众号：玖的数学天地MathUniverse

学会动脑子（

前言：你怎么知道我这场拿了一血，然后各种犯病代码到结束。

评价：题适中难度，区分度较明显，个人题解不包含E题、J题（理论上，能想明白但是说不清J）。

J 理论上来说是中档题，不至于3 / 81

L 经典原题

评价：题简单，适合萌新，部分题面理解有点绕，基本上都是板子应用题。

Codeforces Global Round 26

除法

对于两个整数 a , b ,存在两个唯一的整数 q , r 满足：

$$b= aq + r$$​

当 r = 0 时，我们称 a 整除 b , 记作 a | b， 称 a 为 b 的约数

算术基本定理

n的质因数分解唯一。

Π(n) 表示 小于等于 n的素数个数。

约定下面公式中 p 为素数

$$\displaystyle \lim_{n\rightarrow \infty} \frac{\pi(n) }{\frac{n}{\ln n}} = 1$$

$$P_n = O(n\log n)$$

$$\displaystyle \sum_{i = 1} ^ n \frac{1}{i} = O(\log n)$$

$$\displaystyle \sum_{1 \leq p \leq n} \frac{1}{p} = O(\log \log n)$$

整除性质：

$$a | c , b | c, (a,b) = 1 \rightarrow ab | c$$

$$a | bc , (a,b) = 1 \rightarrow a|c$$

$$p | ab \rightarrow p | a或 p | b$$

辗转相除法

$$(a,b) = (a - b, b)$$

$$d | a ,d | b \rightarrow d | (a-b) , d | b$$

$$d | (a,b) 等价于 d | (a-b,b)$$​

时间复杂度：log min(a,b)

特别的：

如果 a,b 都是奇数，那么 (a,b) = (a-b,b)

如果 a 是偶数，b 是奇数，那么 (a,b) = (a / 2,b)

如果 a,b 都是偶数，那么 (a,b) = 2(a / 2,b / 2)

裴蜀定理

对任意整数 a , b , d , (a , b) | d ，存在整数 u , v 使得 ua + vb = d

扩展欧几里得

$$\displaystyle a\mod b = a - \lfloor{\frac{a}{b}}\rfloor b$$

由归纳法假设存在 u’ , v’ 使得 u’ b + v’ (a mod b) = d

即

$$\displaystyle u’b + v’(a - \lfloor{\frac{a}{b}}\rfloor) b = d$$

$$\displaystyle v’a + (u’ - \lfloor{\frac{a}{b}}\rfloor v’) b = d$$

于是就有了 (a,b) 的解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int exgcd(int a,int b,int &x,int &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    // int xx,yy;
    // int d = exgcd(b,a % b,xx,yy);
    // x = yy;
    // y = xx - (a / b) * yy;

    int d = exgcd(b,a % b, y, x);
    y -= (a / b) * x;
    return d;
}