很多折纸的第一个部分都是打格子（把正方形的一边$n$等分）。容易发现，如果$n=2^k$，这是很容易完成的；但很多时候$n$是个很棘手的素数（在现代折纸里，小于$100$的$n$都不算稀奇，超过$100$的也不是没有）；当然这肯定不算问题：别说折纸了，别说尺规作图了，就算是直尺作图，有两条平行线之后，就能任意线段$n$等分了（等价于解一次方程的能力）。但用折纸作图的方法去$n$等分会让纸变得很乱，有很多多余的折痕，对后续的折制过程和成品的美观度都不利，因此我的做法一般是，量一下纸有多宽，算出一格有多长，然后拿笔在纸边缘做上一些标记。
但是做标记的过程还是需要反复用尺子测量的，也很繁琐，所以我就提出了如下的问题：假设纸的边缘是$[0,1]$这个区间，如果在$x=a$处有折痕，我就可以做出$x=\dfrac{a}2$处的折痕和$x=\dfrac{1+a}2$处的折痕（分别代表用纸的左右两侧边缘去对折到$x=a$处的折痕）；当然，还可以直接对折整张纸，得到$x=\dfrac12$处的折痕。除此之外，我还可以做一些标记，在$x=a_1,a_2,\dots,a_m$处直接给出折痕；再限制不能出现多余的折痕（比如不能用$14$等分的方法得出$7$等分），那么我最少要做多少个标记（最小化$m$），才能将纸的边缘$n$等分呢？
比如当$n=2^k$，答案就是$m=0$，因为完全不需要做标记就能用对折再对折的方法完成$n$等分；而当$n=5$时，答案就是$m=1$，只需要在$x=\dfrac45$处做出折痕，然后把纸的左边缘折到$x=\dfrac45$处，就能得到$x=\dfrac25$处的折痕；再次对折就能得到$x=\dfrac15$处的折痕；最后把右边缘折到$x=\dfrac15$处，就能得到$x=\dfrac35$处的折痕，完成$5$等分。
使用图论的朴素解决方案
我心血来潮想到这个问题之后，第一反应就是写个程序来看看比较小的$n$的情况。那么程序该怎么写呢？容易想到，只需要把$x=\dfrac1n,\dots,\dfrac{n-1}{n}$这$n-1$条折痕建成$n$个点，把每条折痕向从它可以对折得出的折痕连边，就能得到一张有向图；按照定义，每个点的出度不超过$2$，因此是$O(n)$条边的一张图。因此我们的问题就转化成了一个图论问题，即：给一张有向图$G$，并且可能会给一个点$a_0\in V$（对应当$n$是偶数时，可以直接得到$x=\dfrac 12$这个位置），要求选择尽量少的$m$个点$a_1,\dots,a_m\in V$，使得$\forall v\in V,\exists k\in 0\dots m$，使得$G$中存在$a_k$到$v$的路径。
而这个图论问题是相当简单的，哪怕是提高组小朋友也可以秒切：只需要把$G$的全部强连通分量缩成点，得到一个DAG，这个DAG中入度为$0$点的个数（可能要排除$a_0$所在的强连通分量）就是答案。这是非常显然的，不解释了。因此我很快就写完了一个在$O(n)$的时间之内求出答案的程序，得到了答案的数列（从$n=2$开始）：$0,1,0,1,1,2,0,2,1,1,1,1,2,4,\dots$
按照我探究问题的一般方法，下一步当然是把这个数列放到OEIS里搜索，看看它到底有什么规律。很可惜，OEIS上什么搜索结果都没有。但根据我的某种直觉，我尝试将数列中的每一项都加上$1$，再在OEIS上查询，居然就查到了结果，并且这个数列的编号还特别小：A000374！
数论的解释
按照OEIS的说法，我们的答案就是$f(x)=2x\bmod n$这个映射的循环的个数（再减去1）。这是为什么呢？
原来，是我们按照直觉的建图方式，其实没有抓住问题的本质。在我们建的图中，一个点可能没有出边，也可能有一条或者两条出边，这是相当不规则的；但是注意到我们只关心这张图的强连通分量，而众所周知，一张图的强连通分量和其“反图”（所有边指向全部逆转）的强连通分量是相同的，因此只需要研究“反图”的性质。
反图的边是什么呢？原图中有$x$指向$\dfrac{x}{2}$的边，以及$x$指向$\dfrac{x+n}{2}$的边，这分别对应反图中$\dfrac{x}{2}$指向$2\cdot \dfrac{x}{2}$的边，和$\dfrac{x+n}{2}$指向$2\cdot\dfrac{x+n}{2} - n$的边。因此反图中，一个点$y$的出边只能有$2y$或者$2y-n$两种可能，而它们中必定有且仅有一种（例外后文会解释）是在$1,2,\dots, n-1$这个区间之中的。这就说明反图是每个点只有一条出边的图：基环内向树！并且出边就是$2y\bmod n$！而原图中“入度为零的强连通分量”，就对应反图中“出度为零的强连通分量”，即环的个数！
那又是为什么要减去$1$呢？而且$n$是偶数的情况，可以直接得到第$\dfrac{n}{2}$号点，这还对应反图中一个出度为零的点，不就不是基环内向树了吗？这是因为从$1$开始标号的坏习惯在作乱。加入一个$0$号点，并且讨论$0$号点所在的强连通分量（它显然没有出度），即可完美解决这两个偏差。
更快的做法
现在我们知道了答案的一个简洁的表示，自然希望能够得出一个比$O(n)$更快的做法。为此，我们需要对$f(x)$这个映射的性质进行更深入的研究。
首先，可以将$n$写成$2^kn’$的形式，其中$n’$是一个奇数。我们有答案$m(n’)=m(n)$。这是为什么呢？$\forall x\in 0\dots n-1$，必然有$2^k\mid f^{(k)}(x)$（这是因为$f^{(k)}(x)=2^kx+qn$，且$2^k\mid n$）。$x$最终所在的循环一定是$f^{(k)}(x)$最终所在的循环，并且，$f^{(k)}(x)$在模$n$意义下最终所在的循环显然就是$\dfrac{f^{(k)}(x)}{2^k}$在模$\dfrac{n}{2^k}$即$n’$下最终所在的循环。每个模$n$下的循环都被考虑过了，这就说明模$n$下循环的个数不会多于模$n’$下循环的个数。另一方面每个模$n’$下的循环显然都能被某个模$n$下的循环对应到（只需将每个循环元素乘上$2^k$即可），这就说明两种循环个数是相同的。
因此只需要考虑$n$是奇数的情况。此时$f$的性质就很好了：它是群$\mathbb{Z}_n$的一个自同构。因此在$f$的作用下群中的每个元素都会在某个循环（cycle）里（对应基环内向树仅由若干个环组成），因此可以去掉“最终”二字，这样统计环的个数就方便多了。
设$x\in\mathbb{Z}_n$，并且$\gcd(x,n)=g$，那么显然$\forall k$ ， $\gcd(f^{(k)}(x),n)=\gcd(2^kx,n)=\gcd(x,n)=g$（由于$n$和$2^k$互质）。这就说明$x$所在的模$n$意义下的循环，就对应于$x’=\dfrac{x}{g}$所在的模$n’=\dfrac{n}{g}$下的循环；并且$x’$所在的循环中全部元素都与$n’$互质。而$x’$是模$n’$可逆的元素，这就说明$x’$所在的循环，与$1$所在的循环可以对应，即其长度为$o_2(n’)$，即元素$2$在群$\mathbb{Z}_{n’}$中的阶数。而我们已经知道了，这样的元素$x$一共有$\phi(n’)$个；由于它们全部位于循环之内，并且每个循环的长度都是$o_2(n’)$，循环两两不交，并集就是模$n’$的完全剩余系。这就说明我们将这$\phi(n’)$个元素不重不漏地分成了一些大小为$o_2(n’)$的集合，集合的个数自然是$\dfrac{\phi(n’)}{o_2(n’)}$了。
由于每个$x$都对应唯一的一个$n’$，循环的总个数自然就是$\sum_{n’}\dfrac{\phi(n’)}{o_2(n’)}$，即$\sum_{x\mid n}\dfrac{\phi(x)}{o_2(x)}$。这显然是用$O(n^\epsilon)$的时间就能算出来的：这样的$x$只有$O(n^\epsilon)$个，并且对$n$用$O(n^\epsilon)$的时间质因数分解即可求出全部$x$；已经知道了$x$的质因数分解，因此可以用$O(x^\epsilon)$时间求出来$\phi(x)$；而显然$o_2(x)\mid \phi(x)$，只有$O(\phi(x)^{\epsilon})$个可能，逐个尝试（每次尝试都是快速幂，只需$O(x^{\epsilon})$的时间），即可求出来$o_2(x)$。总时间复杂度就是$O(n^\epsilon)\cdot O(n^\epsilon)\cdot O(n^\epsilon)=O(n^\epsilon)$了。
当然，可以做到更快；因为有$\phi(x)\mid \phi(n)$，只需要枚举$\phi(n)$的因数$k$，算出$p=2^k\bmod n$，看看它满足哪些$p\equiv 1\pmod x$即可得出全部$o_2(x)$。然而还是$O(n^\epsilon)$，估计是没有多项式做法的。
