虽然题目不难，但背后蕴含的考点还是很有意思的。

本题的核心考点是唯一分解定理。

此考点曾在NOIP中涉及，非常重要！！！

例如 NOIP2009 Hankson的趣味题

唯一分解定理：设 $p_i$ 表示第 $i$ 个质数，那么对于任意正整数$N$，都有唯一的一组 $a_1,a_2,a_3\dots a_n$ ，使得

$$N=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times\dots\times p_n^{a_n}$$

其中 $a_i$ 可以等于$0$。

用白话文说：任何数都可以表示为他的质因数们的若干次幂的乘积，而幂指数序列是确定的。

推论：对于 $\forall x,y$ ，其中

$$x=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times\dots\times p_n^{a_n}$$

$$y=p_1^{b_1}\times p_2^{b_2}\times p_3^{b_3}\times\dots\times p_n^{b_n}$$

则

$$\gcd(x,y)=p_1^{\min(a_1,b_1)}\times p_2^{\min(a_2,b_2)}\times p_3^{\min(a_3,b_3)}\times\dots\times p_n^{\min(a_n,b_n)}$$

$$\operatorname{lcm}(x,y)=p_1^{\max(a_1,b_1)}\times p_2^{\max(a_2,b_2)}\times p_3^{\max(a_3,b_3)}\times\dots\times p_n^{\max(a_n,b_n)}$$

回到本题，给定整数 $n$ ，求有多少对 $x,y$ ，满足 $\operatorname{lcm}(x,y)=n$ 。

对 $n$ 分解质因数，得到 $n$ 的唯一分解序列 $S=\{a_1,a_2,a_3,\dots,a_n\}$ 。

对于序列中的每一个元素 $a_i$ ，要求 $x,y$ 的分解序列中的对应元素 $x_i,y_i$ 更大的那个与 $a_i$ 相等，另一个可以在 $[0,a_i-1]$ 中任取。

当 $x_i=a_i$ 时， $y_i\in[0,a_i-1]$ ，共 $a_i$ 种方法；

当 $y_i=a_i$ 时， $x_i\in[0,a_i-1]$ ，共 $a_i$ 种方法。

根据加法原理，应有 $d_i=2\times a_i$ 种方法。

然而，刚刚的计算中， $\begin{cases}x_i=a_i\\y_i=a_i\end{cases}$ 的情况被算了两次，因此要减1。

对于分解序列中的其他元素，根据乘法原理，各个质因数直接的方法互不干涉，最终的答案应当是各 $d_i$ 相乘的积

$$\prod_{i=1}^n d_i$$

最后是时间复杂度分析。

计算的瓶颈在于分解质因数，如果使用Pollard_Rho进行分解，时间复杂度为 $O(\sqrt{\sqrt{n}})$ ，非常小的一个数；然而如果用暴力分解质因数，时间复杂度为 $O(\sqrt n)$ ，实际测试中可以通过本题。

实际上，在许多题目中，如果 $n$ 在longlong范围内且没有多组数据， $O(\sqrt n)$ 的时间复杂度是很难TLE的。

所以本题就轻松愉快地解决啦！

总结：

1. 唯一分解定理的内容及其推论，务必牢记

2. 如果组成问题的各个“位”之间相互独立，可以考虑把待求解的问题“按位分解”，这种思想不仅在数论题中十分重要，在动态规划中也经常出现。

AC代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#define re register
typedef long long ll;
using namespace std;

ll n,cnt,ans = 1;

int main(){
	cin>>n;
	for(re int i = 2; i < sqrt(n); ++i){
		cnt = 0;
		while(n%i==0){
			++cnt;
			n /= i;
		}
		if(cnt) ans *= (cnt<<1)+1;
	}
	if(n>1) ans *= 3;//n>1
	cout<<ans<<endl;
	
	return 0;
}