题面
给定一个正整数 n ，求有多少个整数 m∈[1,n) 满足 (n-m)\mid nm 。
解题思路
- 我会枚举！
考虑枚举 [1,n) 的所有 m ，若满足 (n-m)\mid nm ，计数器自增。最后输出该计数器即可。
该算法的时间复杂度为 O(Tn) 。 - 我会数论！
令 k=n-m ，则 k\mid n(k-n) ，由 n(k-n)=nk-n^2 与 k\mid nk 可知 k\mid n^2 。
注意到 k=n-m<n 考虑求出 n^2 中 <n 的因子个数。而当 n\mid m 时，有 \dfrac{m}{n}\mid m 。也就是说，每个 <n 的因数 a 都可以找到一个 >n 的因数 \dfrac{n^2}{a} 。
考虑将 n^2 分解质因数： n^2=p_1^{2i_1}p_2^{2i_2}p_3^{2i_3}⋯p_c^{2i_c} ，根据求因数个数当公式可得因数个数为 (2i_1+1)(2i_2+1)⋯(2i_c+1) 。注意到 n 本身也是 n^2 的因数，所以最后的结果应为 \dfrac{(2i_1+1)(2i_2+1)⋯(2i_c+1)-1}{2} 。
该算法的时间复杂度为 O(T\sqrt{n}) 。