LightOJ - 1236 Pairs Forming LCMPairs Forming LCM（唯一分解定理+LCM）_综合

链接：LightOJ - 1236 Pairs Forming LCMPairs Forming LCM

题意：

给出正整数 $n$ ，问有多少对 $(a, b)$ 满足 $l c m (a, b) = n$ 且 $a\le b\le n$

分析：

这就涉及到gcd和lcm的另一种表示方法了，对于 $a, b$ ，根据唯一分解定理得到标准分解式：

$a=p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3} \cdots p_n^{a_n}$

$b=p_1^{b_1}\cdot p_2^{b_2}\cdot p_3^{b_3} \cdots p_n^{b_n}$

那么有 $\gcd(a,b)=p_1^{\min(a_1,b_1)}\cdot p_2^{\min(a_2,b_2)}\cdot p_3^{\min(a_3,b_3)}\cdots p_n^{\min(a_n,b_n)}$
$lcm(a,b)=p_1^{\max(a_1,b_1)}\cdot p_2^{\max(a_2,b_2)}\cdot p_3^{\max(a_3,b_3)}\cdots p_n^{\max(a_n,b_n)}$
所以对于该题，可以将 $n$ 分解，得到 $n=p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3} \cdots p_n^{e_n}$

先不考虑 $a$ 和 $b$ 的大小关系；

对于 $p_i$ ， $a_i$ 和 $b_i$ 要至少有一个等于 $e_i$ ，另一个要 $\le e_i$ ，所以共有 $2*(e_i+1)-1=2e_i+1$ 种搭配；（ $? 1$ 是因为 $a_i=b_i=e_i$ 多算了一次）

所以总共的搭配数就是： $res=\displaystyle\prod_{i=1}^{n}(2e_i+1)$

最后，因为 $a\le b$ ，对称分布，所以有 $r e s = r e s / 2 + 1$ 。

以下代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1e7+50;
LL prime[1000000],tot;
bool vis[maxn];
void getprime()
{
    tot=0;for(LL i=2;i<=maxn;i++){
    if(!vis[i])prime[++tot]=i;for(LL j=1;j<=tot&&i*prime[j]<=maxn;j++){
    vis[i*prime[j]]=true;if(i%prime[j]==0)break;}}
}
LL solve(LL n)
{
    LL res=1,k=n;for(LL i=1;prime[i]*prime[i]<=k;i++){
    if(n%prime[i]==0){
    LL e=0;while(n%prime[i]==0){
    e++;n/=prime[i];}res*=2*e+1;}}if(n>1)res*=2*1+1;return res/2+1;
}
int main()
{
    getprime();int T,kase=0;scanf("%d",&T);while(T--){
    LL n;scanf("%lld",&n);printf("Case %d: %lld\n",++kase,solve(n));}return 0;
}