D. 相同 GCD 计数 详细题解

题目核心理解

给定两个整数 $a$ 和 $m$，求满足以下条件的整数 $x$ 的个数：

$$0\le x<m \quad \text{且} \quad \gcd(a,m)=\gcd(a+x,m) $$

数据范围：

• $1\le T\le 50$
• $1\le a<m\le 10^{10}$

---

核心思路

1. 关键性质

• 由模运算性质，$a+x \bmod m$ 会取遍 $[0,m-1]$，问题等价于统计 $\gcd(k,m)=\gcd(a,m)$ 的 $k$ 的个数。
• 设 $g = \gcd(a,m)$，令 $a = g\cdot a'$，$m = g\cdot m'$，则 $\gcd(a',m')=1$。
• 条件 $\gcd(k,m)=g$ 等价于 $\gcd(k/g,\ m')=1$。

2. 转化规则

所求答案等价于： 在 $0\le k<m'$ 中与 $m'$ 互质的整数个数，也就是欧拉函数 $\boldsymbol{\phi(m')}$。

3. 欧拉函数计算

对 $m'$ 做质因数分解 $m'=\prod p_i^{e_i}$，则：

$$\phi(m')=m'\cdot\prod_{p\mid m'}\left(1-\frac1p\right) $$

---

算法流程

1. 对每组 $a,m$，计算 $g = \gcd(a,m)$。
2. 计算 $m' = m/g$。
3. 对 $m'$ 进行质因数分解。
4. 按公式计算欧拉函数 $\phi(m')$，即为答案。

---

公式与复杂度分析

最终答案公式：

$$ans = \phi\left(\frac{m}{\gcd(a,m)}\right)$$

复杂度

• 质因数分解：$O(\sqrt{m})$
• 单次测试用例：$O(\sqrt{m})$
• 总复杂度：$O(T\sqrt{m})$

可轻松处理 $m\le 10^{10}$、$T\le 50$ 的数据范围。