素数无穷个的证明

方法1 设: $n \ge 0$, $F_n=2^{2^n}+1(Fermat\ Number)$ ,设 $n\neq m$ ,若 $d > 1,d \mid F_n$ 则 $d$ 不整除 $F_m$ 。 证明: 不妨设 $m>n$,则有 $$ F_n \mid F_m -2 = 2^{2^m}-1=(2^{2^{n}...

Nowcoder 5889 D

题意 给了你一个数组长度 $n$,并规定了 $3$ 种操作次数为 $m$,操作 $1$ 是把一个连续的区间内所有的数字 $x$变为$x^{k} \bmod M$,操作 $2$ 是把一个连续的区间内所有的数字 $x$ 变为$x*k \bmod M$,操作 $...

Nowcoder 5733 M

题意 给定长度为 $n \le 200000$ 的序列,输出下标字典序最大的最长上升子序列 解法 首先 $n$ 这么大,肯定要用 $nlogn$ 的方法进行维护。那么难点在于下标字典序最大。 注意到一点,我们维护的数组,...

Atcoder ABC 168

E 题意 给定$n \le 2e5$ 个二元组 $(a,b) -1e18\le a,b\le 1e18$ ,若两个二元组 $i,j$ 满足 $a_ia_j+b_ib_j=0$ ,则 $i,j$ 不能同时存在,问有多少种选择方法。 解法 这个形式可以看成是点乘的形式...

NTT

在 $\text{FFT}$ 中,我们使用复数的单位根进行 $DFT$,这样会产生浮点数误差。对于只有整数参与的多项式运算,我们需要找到正好的方法。 引入 考虑 $\text{FFT}$ 的时候我们为什么选择使用复数单位根。 $...

欧拉函数

在数论中,对 正整数 $n$, 欧拉函数 $\phi(n)$ 是 小于等于 $n$ 的正整数中与 $n$ 互质的数的数目。 求欧拉函数值 首先我们考虑素数的欧拉函数值,素数肯定与小于本身的正整数互质,所以 $\phi(p)=p-1$ ...

FFT

点值表示法 $n$个二维平面上的点$(x_1,y_1)…(x_n,y_n)$,确定了唯一一个过这些点的 $n-1$次多项式。 证明:设 $n-1$ 次多项式 $f(x),g(x)$ 都经过这 $n$ 个点,设 $n-1$ 次多项式 $y(x)=f(x)-g(x)$,那么$y(...

CDQ 分治

逆序对-梦开始的地方 题目:给定序列$s,|s|\leq 1e5$,求序列中逆序对的数量 一种解法当然是离散化以后用树状数组求啦. 另外一种方法就是 归并排序,采用分治的思想,一个区间中全部的逆序对数等于左区...

Atcoder ABC 160

E 题意 你有$a\leq 1e5$个红球,$b\leq 1e5$绿球,$c \leq 1e5$个白球,每个球都有自己的价值.你要从中选$d\leq a$红球,$e\leq b$绿球,把一个白球染成红球或者染成绿球.求你能得到的最大价值 解法 枚举...