\(\forall p \in \mathbb P, 0 \le a \lt p, a^{p-1} \equiv 1 \pmod{p}\)
证明略。
\(\forall p \in \mathbb P, 0 \le x \lt p\)，方程 \(x ^ 2 \equiv 1 \pmod p\) 的解为 \(x \equiv \pm 1 \pmod p\)。
证明略。
设我们要检测的数为 \(n > 2\)。显然 \(n\) 为奇数，设 \(n - 1 = 2^s t\)，其中 \(t\) 为奇数。
若 \(n\) 为素数，我们希望 \(\forall a \in [1,n)\)，满足以下任意条件：
\(a^t \equiv 1 \pmod n\)。
\(\exists r \in [0,s), a ^ {2 ^ r t} \equiv -1 \pmod n\)。
对于一个已知的合数 \(n>3\)，我们的目标是快速找到它的一个非平凡因子（除 \(1\) 和 \(n\) 外）。
显然问题可以转化为找到一个 \(k\) 使得 \(1 \lt \gcd(k,n) \lt n\)。
考虑一个序列 \(f\)，满足 \(f_0=0\) 且 \(f_i = (f_{i-1}^2 + c) \bmod n\)，其中 \(c\) 是常数。由生日悖论1得 \(f\) 中不同的数量的期望为 \(O(\sqrt n)\)。
设 \(m\) 是 \(n\) 的最小质因子，显然有 \(m \le \sqrt n\)。
设 \(g_i = f_i \bmod m\)，则 \(g\) 中不同的数量的期望为 \(O(\sqrt m)\)。
于是我们可以在期望 \(O(\sqrt m) \le O(n ^ {\frac 1 4})\) 的时间内找到两个位置 \(i,j\) 使得 \(f_i \not = f_j \land g_i = g_j\)，即 \(n \nmid (f_i - f_j) \land m \mid (f_i - f_j)\)，于是有 \(1 \lt m \le \gcd(|f_i - f_j|, n) \lt n\)
于是我们可以在期望 \(O(n ^ {\frac 1 4})\) 的时间内找到 \(k\) 满足 \(1 \lt gcd(k,n) \lt n\)，也就找到了一个 \(n\) 的非平凡因子。
已知有 \(n \le 8500\) 个基地，以及开启它们的顺序排列 \(p\)，初始所有基地都关闭。
求一个整数序列 \(f\) 使得在任意时刻，已开启的基地的 \(f\) 值按顺序排成的序列满足：
任意子段都有一个只出现在其中过一次的值（以下记为合法）
\(\forall i, f_i \in [1,24]\)
默认文中的形如 \([l,r)\) 的区间为其与整数集的交集。
设原多项式为 \(F(x) = \sum_{i \in [0,n)} a_i x ^ i\)，其中 \(n = 2 ^ k, k \in \mathbb Z ^ +\)。
我们要求 \(\forall i \in [0,n),\hat a_i = F(t_i)\)，其中 \(t\) 是一个长度为 \(n\) 且两两互不相同的序列。
显然 \(F\) 可以被一组 \(\hat a,t\) 唯一确定，即点值表示法。
设点 \(A(x,y)\) 绕原点 \(O(0,0)\) 逆时针旋转 \(\beta\)，则设在极坐标系下 \(A\) 的坐标为 \((r,\alpha)\)
这意味着 \(x=r \cos \alpha, y=r \sin \alpha\)
目标点 \(A'(x',y')\) 的极坐标即为 \((r,\alpha + \beta)\)
展开（其中 \(\sin\) 和 \(\cos\) 的展开参考 here）：
本文中使用 \(\cap\) 表示按位与，用 \(\cup\) 表示按位或
给定长度为 \(2^n\) 的数列 \(A,B\)，求 \(C_i = \sum_{j \cup k = i} A_j \times B_k\)
显然有 \(O(4^n)\) 的暴力
这一部分可以参考 FMT 中的 Zeta 变换 ，即定义 \(\hat A_i\) 为序列 \(A\) 中 \(i\) 的子集和
考虑分治
对于长度为 \(2^n\) 的待求解的 \(\hat A\)，我们把它分成独立的两部分，即 \([0,2^{n-1})\) 和 \([2^{n-1},2^n)\) 两个区间分别求解
然后考虑这两个区间之间的贡献，发现只有 \([0,2^{n-1})\) 对 \([2^{n-1},2^n)\) 有贡献，于是对于 \(i \in [0,2^{n-1})\)，将 \(\hat A_{i}\) 加到 \(\hat A_{i+2^{n-1}}\) 中即可
时间复杂度 \(O(n 2^n)\)