The Number of Pairs

Yorg / 2024-10-10 / 原文

算法

数据范围一眼数学题
~~然而考场并没有思路~~

这一类题显然要将 $\gcd{(a, b)}$ 消掉或者表示 ( $\rm{lcm}{(a, b)}$ 可以用 $\gcd{(a, b)}$ 表示)

考虑 $a = \gcd{(a, b)} * k_1$ 和 $b = \gcd{(a, b)} * k_2$
开始化简

然后可以求出 $\rm{lcm}{(a, b)} = \frac{k_1 \times k_2 \times x}{c \times k_1 \times k_2 - d}$

问题转化成已知 $\rm{lcm}$ 和 $\rm{gcd}$, 求 $a, b$ 的种数

考虑 $\gcd{(a, b)} = \frac{x}{c \times k_1 \times k_2 - d}$
推出 $\gcd{(\frac{a}{\frac{x}{c \times k_1 \times k_2 - d}}, \frac{b}{\frac{x}{c \times k_1 \times k_2 - d}})} = 1$
设 $y = c \times k_1 \times k_2 - d$
化简, 得 $\gcd{(\frac{a \times y}{x}, \frac{b \times y}{x})} = 1$
又有 $k_1 \times k_2 = \frac{y + d}{c}, \rm{lcm}{(a, b)} = \frac{\frac{y + d}{c} \times x}{y \times c}$
同化简 $\gcd$ 的方法推出 $\rm{lcm}(\frac{a \times y}{x}, \frac{b \times y}{x}) = \frac{y + d}{c}$
问题就变简单了

转化为唯一分解定理后可以知道, 将 $\frac{y + d}{c}$ 分解之后, 对于每个质因数, 要么给$a$, 要么给$b$, 所以答案为 $2 ^ {Num}$ ( $Num$ 为质因数个数)
观察前面的柿子, 得出

\[y \mid x \]

所以枚举 $x$ 的因子 $y$, 对于每一个因子 $y$, 检查 $c \mid y + d$, 记录 $\frac{y + d}{c}$ 的值并且分解质因数, 完事

本质不同质因数个数这个函数是可以线性筛的。线性筛预处理完，然后枚举 $x$ 的约数，接着判断 $\dfrac{d + y}{c} $ 是否为整数，最后加上贡献即可