题解：P17225 [Math×Girl²] 算术课堂
Galois_Field_1048576
·
·
题解
声明: 写作过程中多次使用 AI 检验并修改病句、斟酌用词与行文,
论证的展开亦有 AI 参与;
思路均出自魔女の理团队的各出题人、验题人及我的个人理解.
约定. 根据个人习惯, 所有数组下标从 0 开始.
这可能影响你对奇数位置等术语的理解.
总结. 固定 (r,s) 后, 若 Q\ne0, 只需检查 D\mid10^\ell-1. 按比例因子 t
去重后, 直接按 \operatorname{ord}_D(10)\mid\ell 统计;
较短的长度逐一检查. P=Q=0 时得到的等差数列另行合并.
题目描述. 给定既约真分数 \dfrac NM. 若在分数 \dfrac AB
的分子、分母中各删去一段连续且相同的十进制串后, 恰好得到 \dfrac NM,
则称 \dfrac AB 为一个合法的原分数. 求分母位数不超过 K
的原分数的个数.
下文中, “数” 一律按十进制字符串理解, 允许在前面补足前导零; 例如长度为
一次删除操作由位置对 $(r,s)$ 和长度 $\ell$ 唯一确定: 删去后保留 $N$ 的末
$r$ 位和 $M$ 的末 $s$ 位, 即 $$N=a\cdot10^r+b,\qquad M=c\cdot10^s+d,$$
其中 $0\le b<10^r$, $0\le d<10^s$, $0\le r\le|N|$, $0\le s\le|M|$;
位置对共 $(|N|+1)(|M|+1)$ 个.
被删去的字符串长度为 $\ell$, 数值为 $x$. 若 $r=|N|$ 或 $s=|M|$,
则删除串位于相应数的开头, 最高位必须非零; 其余情形允许前导零.
原分母的位数恰比 $M$ 多 $\ell$, 故分母位数不超过 $K$ 等价于
$|M|+\ell\le K$. 令 $L=K-|M|$, 只需统计 $1\le\ell\le L$; 若 $L\le0$,
则没有贡献.
记 $u=(N,M)^{\top}$, $v=(b,d)^{\top}$, $w=(10^r,10^s)^{\top}$. 删去前,
原分数的分子、分母所组成的向量为 $$A=10^\ell u-(10^\ell-1)v+xw.$$
删去前的分子由 $a,x,b$ 三段依次拼接而成, 数值为
$a\cdot10^{r+\ell}+x\cdot10^r+b$. 由 $N=a\cdot10^r+b$ 可将它写成
$10^\ell N-(10^\ell-1)b+x\cdot10^r$; 分母同理.
删去前后分数相等, 当且仅当 $A$ 与 $u$ 共线. 展开 $\det(u,A)$, 由
$\det(u,v)=P$, $\det(u,w)=-Q$ 得 $\det(u,A)=-(10^\ell-1)P-xQ$,
故共线等价于 $$xQ=-(10^\ell-1)P,$$ 其中 $$P=\det(u,v)=Nd-Mb,\qquad
Q=-\det(u,w)=M\cdot 10^r-N\cdot 10^s.$$ 下文只需使用 $(P,Q)$.
先设 $Q\ne0$, 记 $g=\gcd(P,Q)$, $D=|Q|/g$.
由 $xQ=-(10^\ell-1)P$, 可得 $$x=-\frac{(10^\ell-1)P}{Q}.$$
它为整数当且仅当 $Q\mid P(10^\ell-1)$. 除以 $g$ 后, 因
$\gcd(P/g,Q/g)=1$, 这等价于 $D\mid10^\ell-1$; 此时 $x$ 也随之确定.
$10^\ell-1$ 与 $10$ 互素, 所以 $D$ 含因子 $2$ 或 $5$ 时没有这样的
$\ell$. 否则 $10$ 在模 $D$ 意义下可逆, 且 $D\mid10^\ell-1$ 当且仅当
$\operatorname{ord}_D(10)\mid\ell$. 约定 $D=1$ 时
$\operatorname{ord}_D(10)=1$.
记 $C=-P/Q$, 则 $x=C(10^\ell-1)$. 由 $0\le x<10^\ell$ 可知, $C<0$ 或
$C>1$ 时没有贡献, 以下设 $0\le C\le1$. 再考虑删除串位于开头的情形:
此时要求 $x\ge10^{\ell-1}$, 即 $C\cdot(10^\ell-1)\ge10^{\ell-1}$, 等价于
$$C\ge\frac{10^{\ell-1}}{10^\ell-1}=\frac1{10}\left(1+\frac1{10^\ell-1}\right),$$
右端随 $\ell$ 严格递减. 因此只要某个长度满足该不等式, 更长的长度也满足.
按 $C$ 的取值分情况讨论:
- 若 $C\le1/10$, 则右端恒大于 $1/10$, 条件恒不成立;
- 若 $C>1/10$, 写 $C=p/q$ 为既约分数, 则 $p\le|P|$ 且 $10p-q\ge1$,
条件等价于 $10^{\ell-1}(10p-q)\ge p$. 左边至少为 $10^{\ell-1}$, 故
$\ell\ge\lfloor\log_{10}|P|\rfloor+2$ 时该条件恒成立;
- 若 $C=0$, 则 $x=0$: 开头情形不合法, 其余情形只须 $D\mid10^\ell-1$.
据此, 对 $\ell\le\lfloor\log_{10}|P|\rfloor+2$ 的长度逐一检验;
更大的长度只须满足 $\operatorname{ord}_D(10)\mid\ell$.
再按 $Q$ 的取值分情况讨论:
- 若 $Q=0$ 而 $P\ne0$, 则共线条件无解;
- 若 $P=Q=0$, 则共线条件恒真: 非开头情形 $x$ 可在 $[0,10^\ell)$ 中任取,
开头情形则须 $x\ge10^{\ell-1}$, 取法数分别为 $10^\ell$ 与
$9\cdot10^{\ell-1}$.
对单个位置对, 在 $1\le\ell\le L$ 上求和, 得
$$\sum_{\ell=1}^L10^\ell,\qquad
\sum_{\ell=1}^L9\cdot10^{\ell-1}=10^L-1.$$
单个位置对的答案不能直接相加, 应先按比例因子 $t$ 去重: 由于 $N/M
已既约, 每个原分数唯一地写成 \frac AB=\frac{tN}{tM}. 对 Q\ne0
的位置对, 由 t=A/N 及前面的 x 的表达式得 t=\lambda 10^\ell+\mu,
其中 \lambda=1-\frac bN-\frac{10^rP}{NQ},\qquad
\mu=\frac bN+\frac{10^rP}{NQ}.
两个位置对在同一长度 \ell 下产生同一分数, 当且仅当它们给出的 t
值相等. 分两种情况:
-
若 (\lambda,\mu)\ne(\lambda',\mu'), 则 t=t' 推出
故至多一个 $\ell$ 满足;
-
若 (\lambda,\mu)=(\lambda',\mu'), 则完全重合.
把 (\lambda,\mu) 约分后相同的位置对放在一起. 若 C\notin[0,1] 或
进而不产生任何贡献.
对同一组 $(\lambda,\mu)$, 每个位置对对应一个阶. 令这些阶的最小公倍数为
$T$. 当 $\ell>\lfloor\log_{10}|P|\rfloor+2$ 时, 恰有 $T\mid\ell
的长度产生原分数; C=0 时将这一界取为零.
不同的 (\lambda,\mu) 组只可能在较短长度时产生相同的 t. 把
$10^{2(|N|+|M|)+2}$. 若两个不同组在长度 $\ell$ 给出相同的 $t$, 则
$10^\ell=(\mu'-\mu)/(\lambda-\lambda')$ 是绝对值至多
$2\cdot10^{4(|N|+|M|)+4}$ 的整数之比, 所以 $\ell\le4(|N|+|M|)+4$.
对不超过这个界的 $\ell$ 逐一比较 $t$; 更长时各组互不相交, 每组贡献
$$\max\left\{0,\ \left\lfloor\frac LT\right\rfloor-\left\lfloor\frac{4(|N|+|M|)+4}{T}\right\rfloor\right\}.$$
剩下 $P=Q=0$ 的位置对, 先看其取值情况. 由 $Q=0$ 得
$M\cdot10^r=N\cdot10^s$, 因 $\gcd(N,M)=1$ 有 $N\mid10^r$. 固定 $\ell
时, t 随 x 以整数 10^r/N 为公差递增, 首末两项都是 10^\ell
的一次式 (端点来自 0、10^{\ell-1}、10^\ell).
一次式两两至多相交一次, 故任意两个端点的大小关系至多在一个 \ell
处反转; 按交点分段后, 每段内并集的长度都是 10^\ell 的线性函数,
直接求和即可.
还要与 P=Q=0 的位置对合并, 否则可能重复计数. 此时 N=1, M=10^m
(m\ge1), 位置对为 (r,r+m), 且 b=k, d=10^m k. 给定
t=\lambda10^\ell+\mu$, 它落在相应等差数列中当且仅当 $t-(1-k)10^\ell-k
被 10^r 整除, 且商在 x 的取值范围内. 当 \ell\ge r 时,
因而短长度逐一检查即可; 对其余长度, 每一对 $(\lambda,\mu)
与位置对要么总是重合, 要么从不重合. 前一种情形中,
从该组的计数中减去相应部分即可. 这样的对至多 (|N|+1)(|M|+1)^2 个.
最后处理阶 \operatorname{ord}_D(10). 对 D 与 \varphi(D)
分别试除分解, 即得 \varphi(D) 及其质因数分解.
令 u=\varphi(D). 若 u 仍是 o=\operatorname{ord}_D(10) 的倍数,
则对质因子 p, 10^{u/p}\equiv1\pmod D 当且仅当 p\mid u/o.
因此只要同余成立就将 u 除以 p; 全部处理完毕后 u=o, 即得
分解所需时间为 $\mathrm O(\sqrt D)$, 求阶需 $\mathrm O(\log|Q|)$ 次幂,
因此位置对 $(r,s)$ 需 $\mathrm O(\sqrt{|Q|}+\log^2|Q|)$ 次运算. 由
$$\sqrt{|Q|}\le\sqrt{M10^r}+\sqrt{N10^s}$$ 知, 对所有位置对求和后,
分解部分的时间为 $$\mathrm O\left((|N|+|M|)10^{(|N|+|M|)/2}\right).$$
求阶部分的时间不超过 $\mathrm O\bigl(|N|\cdot|M|\cdot(|N|+|M|)^2\bigr)$,
可被上式包含. 故总时间复杂度为
$\mathrm O\left((|N|+|M|)10^{(|N|+|M|)/2}\right).