为什么这几天想要写博客呢？
因为感觉自己也没有几天了，现在多写一些至少证明自己涉足过OI这个领域
# 题面
若记 $a,b$ 的「NIM积」为 $a\odot b$，则有以下性质：
- 对于任意正整数 $k$，数集 $A_k=\{x\mid x\in\mathbb{N},x<2^{2^k}\}$ 满足 $\forall x,y\in A_k,x\odot y\in A_k$（运算在 $A_k$ 内封闭）；
- $a\odot 1=a$（单位元）；
- $a\odot 0=0$（零元）；
- $a\odot b=b\odot a$（交换律）；
- $(a\odot b)\odot c=a\odot(b\odot c)$（结合律）；
- $a\odot(b\otimes c)=(a\odot b)\otimes(b\odot c)$，其中 $\otimes$ 是按位异或（分配律）；
记 $a^{\odot b}=\overbrace{a\odot a\odot a\odot\cdots\odot a}^{b个}$。给定 $a,b$ 求解方程：
多组询问，每次给定 $a,b$。数据规模：$a,b< 2^{64}$，数据组数不超过 $100$。
# 解析
不是很清楚「NIM积」的一些技巧，所以此篇不涉及「NIM积」计算的优化。
另外本篇中极有可能有不严谨的地方 ╯︿╰ 希望各位能指出
记数集 $A=\{x\mid x\in[1,2^{64}),x\in\mathbb{N}^+\}$。（注意排除了 $0$）
根据NIM积的上述性质，可以推断 $(A,\odot)$ 是乘法群（满足封闭性、结合律、有单位元和逆元）。以下简记「NIM积」为「乘法」。
群的大小（数集的大小为）记为 $F=2^{64}-1$，则有 $\forall a\in A,a^F=1$（可以类比整数模 $n$ 乘法群）。
回过头来看题目给定的问题
是一个离散对数的经典模型。但是数集大小 $F$ 太大，并不能 $O(\sqrt F)$ 用 BSGS 暴力求解。
观察到 $F$ 并非素数，实际上质因数分解得到
这些质因子都不大，考虑能否对单个质因子求解，然后得到原问题的答案。
比如对质因子 $p$ 单独求解。不妨设 $x=kp+r$，则：
经过下列推导（注意 $p\mid F$）：
上述方程有两个未知数 $k,r$。但是因为 $a^F=1$，有
类似的，定义 $a$ 的阶 ${\text{ord}} a$ 为满足 $a^k=1$ 的最小正整数 $k$，则
（抱歉，不知道博客渲染出了点啥问题，上图的文字就是渲染不出来，只能截图将就一下了 QwQ）
因此 ${\text{ord}} a^{\frac{F}{p}}=\frac{p}{F}{\text{ord}} a\le p$。也就是说，如果 $\Big(a^{\frac{F}{p}}\Big)^{r}=b^{\frac{F}{p}}$ 的解 $r$ 存在，那么必然存在特解 $r=r_0$，$r_0\le p$。
$p$ 较小，可以直接 BSGS $O(\sqrt{p})$ 的复杂度内求解。
解出 $r$ 后，有：
$a^{-r}=a^{F-r}$，类似于费马小定理求逆元。于是转化为子问题，$a’=a^p$，$b’=b\cdot a^{-r}$，求解未知数 $k$。
记对第 $i$ 个质因子执行上述过程后得到的方程是
其中 $k_i$ 是未知数。于是有 $a_i=a_{i-1}^{p_i},b_i=b_{i-1}\cdot a^{-r_i}$，$k_i=k_{i+1}p_{i+1}+r_{i+1}$。
对每个质因子都做一次上述过程后，最后我们会得到一个关于 $k_7$ 的方程 $a_7^{k_7}=b_7$。这个方程如何求解？
实际上这个方程不需要求解——$a_7=a^{p_1p_2\cdots p_7}=a^F=1$，此时若 $b_7=1$，则有无穷解，取朴素解 $k_7=1$；若 $b_7\neq1$，则无解。
然后 $k_i=k_{i+1}p_{i+1}+r_{i+1}$ 往回代，代出 $k_1$，然后得到 $x=k_1p_1+r_1$。
# 源代码
1 | /*Lucky_Glass*/ |