GCD and LCM HDU - 4497

本文主要是介绍GCD and LCM HDU - 4497，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=4497

将gcd与lcm素因子分解 如果gcd某个素因子的幂次pi大于lcm对应素因子的幂次qi 那就是凑不出 因为gcd肯定是lcm因子

如果pi<=qi xyz三个数中必有一个幂次为pi 必有一个为qi 因为gcd就是取得三者最小 lcm取最大 只剩一个数的幂次ti可变 当ti=pi或ti=qi时 可以产生3!/2!种可能 意思是把这三个幂次全排列一下 当ti!=pi且ti!=qi时 则产生3!种可能 幂次内加法原理 幂次之间乘法原理即可

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e2+10;int main()
{ll a1[maxn],a2[maxn],p1[maxn],p2[maxn];ll gcd,lcm,ans;int t,n1,n2,i,j,flag;scanf("%d",&t);while(t--){scanf("%lld%lld",&gcd,&lcm);n1=0;for(i=2;i*i<=gcd;i++){if(gcd%i==0){n1++;a1[n1]=i,p1[n1]=0;while(gcd%i==0){gcd/=i;p1[n1]++;}}}if(gcd!=1){n1++;a1[n1]=gcd,p1[n1]=1;}n2=0;for(i=2;i*i<=lcm;i++){if(lcm%i==0){n2++;a2[n2]=i,p2[n2]=0;while(lcm%i==0){lcm/=i;p2[n2]++;}}}if(lcm!=1){n2++;a2[n2]=lcm,p2[n2]=1;}/*printf("***%d***\n",n1);for(i=1;i<=n1;i++){printf("%lld %lld\n",a1[i],p1[i]);}printf("***%d***\n",n2);for(i=1;i<=n2;i++){printf("%lld %lld\n",a2[i],p2[i]);}*/i=1,j=1,flag=1,ans=1;while(i<=n1&&j<=n2){if(a1[i]<a2[j]){flag=0;break;}else if(a1[i]==a2[j]){if(p1[i]>p2[j]){flag=0;break;}else if(p1[i]<p2[j]){ans*=6*(p2[j]-p1[i]);}i++,j++;}else{ans*=6*p2[j];j++;}}if(i<=n1) flag=0;while(j<=n2){ans*=6*p2[j];j++;}if(flag) printf("%lld\n",ans);else printf("0\n");}return 0;
}

 

这篇关于GCD and LCM HDU - 4497的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---