首页 > 代码库 > 【数论】【最大公约数】【枚举约数】CODEVS 1012 最大公约数和最小公倍数问题 2001年NOIP全国联赛普及组
【数论】【最大公约数】【枚举约数】CODEVS 1012 最大公约数和最小公倍数问题 2001年NOIP全国联赛普及组
对于一对数(p,q)，若它们的gcd为x0，lcm为y0，
则：p*q/x0=y0，即q=x0*y0/p，
由于p、q是正整数，所以p、q都必须是x0*y0的约数。
所以O(sqrt(x0*y0))地枚举约数，依次用gcd判断。
1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 typedef long long LL; 5 LL limit,Q,P,To; 6 int ans; 7 LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);} 8 int main() 9 {10 scanf("%d%d",&P,&Q); limit=P*Q;11 To=sqrt(limit);12 for(LL i=P;i<=To;i++)13 if(limit%i==0)14 if(gcd(i,limit/i)==P)15 ans++;16 printf("%d\n",ans<<1);17 return 0;18 }
【数论】【最大公约数】【枚举约数】CODEVS 1012 最大公约数和最小公倍数问题 2001年NOIP全国联赛普及组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。