设 $f(x) = ax^2+bx+c$, 在域 $\mathbb{Z} / p \mathbb{Z}$ 中何时有根。我们不妨只考虑 $0<a<p$ 的情形。因为
$$ 4af(x) = (2ax+b)^2 - (b^2-4ac) $$
因此我们设 $d = b^2-4ac$，显然可知 $f(x)$ 有根当且仅当 $d$ 是模 $p$ 二次剩余。至于求解也是很简单的事。

在 ACM 竞赛中，由于 C++ 库中没有大数类，手写大数类有些麻烦且写好类接口再应用仍然很麻烦，因此我们经常在有限域 $\mathbb{Z} / p \mathbb{Z}$ 中考虑问题。这里介绍一下 Lucas 定理，及在一类递推关系式中的应用。

快速数论变换（FNT）是环 $\mathbb{Z}/ m \mathbb{Z}$ 上的 Fourier 变换（FFT）。
至于 快速 Fourier 变换是怎样的有什么用处，这里就不多说了，可参考这里。

$\pi(x)$ 表示不超过 $x$ 的素数个数。容易看出可以在 $O(N)$时间复杂度，$O(N)$ 空间复杂度离线预处理求出小于 $N$ 的素数全体。但是如果 $N=10^{12}$ 或者更大，这种做法必然是不现实的。因此下面给出高效的求解方法…

设 $A$ 是(交换)环。令 $X$ 为 $A$ 的素理想全体，定义 $V(E)$ 为 $A$ 中包含 $E$ 的素理想全体，则将所有 $V(E)$ 看做闭集，它满足拓扑空间三条公理，即构成了拓扑，该拓扑称作 Zariski 拓扑，这个拓扑空间叫做环$A$的素谱，记作 $Spec(A)$。
有了拓扑，我们自然要考虑 1.集合的内部、闭包。2.拓扑的基，拓扑的分离性，紧性，3.空间的连通性，不可约性，4.拓扑空间的连续函数等等概念在这个具体拓扑下的样子。

我们知道有理数可以写成有限小数和无限循环小数。无理数必然是无限不循环小数。下面对这个问题详细的分析并且给出相应的有理数转化成小数的代码。

POJ上有一到有趣的题：求一个柱状图中面积最大的矩阵面积为多少?
最暴力的方法当然0.0不值一提，下面看看如何用单调栈的方法解决

关于gcd的博文已经写过三篇了，为什么还要写呢？(任意中文输入法下输入gcd)你就懂了0.0