UVa 10892 LCM Cardinality (数论+组合数学)

本文主要是介绍UVa 10892 LCM Cardinality (数论+组合数学)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVa 10892 LCM Cardinality

---

题目大意:

输入正整数$n$($n \leq 2*10^9$),统计有多少对正整数$a \leq b$,满足$lcm(a,b)=n$.输出n和形成的对数.

题目分析:

(想了好一会儿,orz……)

若将数拆分成唯一分解式,可以发现

设$a=p_1^{k_1}*p_2^{k_2}*...*p_n^{k_n}\\b=p_1^{k'_1}*p_2^{k'_2}*...*p_n^{k'_n}$

则有$gcd(a,b)=p_1^{min(k_1,k'_1)}*p_2^{min(k_2,k'_2)}*...*p_n^{min(k_n,k'_n)}\\lcm(a,b)=p_1^{max(k_1,k'_1)}*p_2^{max(k_2,k'_2)}*...*p_n^{max(k_n,k'_n)}$

那么显然,对于$a$和$b$而言,对于$n$中存在的某一质因数$p_i$则有$max(k_a,k_b)=k_n$.
所以

当$k_a=k_n$时,$0\leq k_b< k_n$,共计$k_n$
当$k_b=k_n$时,$0\leq k_a< k_n$,共计$k_n$

则总共为$k_n*2+1$($+1$的原因是还有$k_a=k_b=k_n$)
当然最后的答案为ans/2+1(只取$a\leq b$情况)

代码:

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>using namespace std;typedef long long ll;int main()
{int n;ll ans;while(scanf("%d",&n)==1&&n) {int m=sqrt(n),t=n;ans=1;for(int i=2;i<=m&&t!=1;i++) if(t%i==0) {int cnt=0;while(t%i==0) t/=i,++cnt;ans*=(cnt*2+1);//指数均为cnt的仅能计算一次 }if(t>1) ans*=3;printf("%d %lld\n",n,ans/2+1);//加上a=b=n的情况 }return 0;
}

这篇关于UVa 10892 LCM Cardinality (数论+组合数学)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---