2025 年贵州预赛

思路

欧拉函数 $\phi (d)$ 数的是一到 $d$ 中与 $d$ 互素的整数。恒等式 ${\sum }_{d\mid N}\phi (d)=N$ 可把一到 $N$ 的整数按与 $N$ 的最大公因数分类证明；奇数和下交换配对没有中点不动元。

想法从哪来：等式同时含和与最小公倍数，先提取两数最大公因数，齐次尺度便能约掉。剩下两个互素正整数，它们的和与积也互素，因此分母要整除固定常数，原来无限的两数搜索就缩成固定常数的有限因数选择。 固定两数之和后，用互素剩余类选择第一个数，另一个由差确定；交换两数不会改变参数值，所以先按无序数对计数。但即使同一和内没有重复，不同因数也可能撞出同一个参数值，需要额外证明。试计算参数值与固定常数的最大公因数，恰能恢复被约出的因数，再由和与积恢复无序数对。这样才能放心累加各因数的计数。

先除去 $a,b$ 的最大公因数，把整除条件落到一对互素数的和上；再由 $\gcd (x+y,xy)=1$ 计数。还需检查不同因数所产生的 $k$ 是否会重合。