最大公约数

例题一：求最大公约数

题目描述

用递归算法求两个数m和n的最大公约数。（m>0,n>0）

输入格式

两个数，即m和n的值。

输出格式

最大公约数。

样例

样例输入

8 6

样例输出

gcd=2

#include<bits/stdc++.h> using namespace std; int a,b; void p(int &c,int &d){ if(d>c){ swap(c,d); } if(d==0){ return; } c=c%d; } int main(){ scanf("%d%d",&a,&b); if(a%b==0){ printf("gcd=%d",b); return 0; } p(a,b); printf("gcd=%d",a); return 0; }

例题二：最大公约数与最小公倍数

题目描述

读入两个整数m、n。编程输出最大公约数和最小公倍数。

输入格式

每组两个数m、n（1≤m,n≤32000）

输出格式

每组两个数，即最大公约数和最小公倍数。保证答案输出不超过1000000000。两数之间有一空格。

样例

样例输入

24 16

样例输出

gcd=8,lcm=48

#include<bits/stdc++.h> using namespace std; int a,b; void p(int &c,int &d){ if(d>c){ swap(c,d); } if(d==0){ return; } c=c%d; } int main(){ scanf("%d%d",&a,&b); int k=a*b; if(a%b==0){ printf("gcd=%d,lcm=%d",b,k/b); return 0; } p(a,b); printf("gcd=%d,lcm=%d",a,k/a); return 0; }

例题三：[NOIP2001]最大公约数和最小公倍数问题

题目描述

输入两个正整数x0,y0(1≤x0＜100000，1≤y0≤1000000),求出满足下列条件的P,Q的个数 (1) P, Q是正整数 (2) 要求P,Q以x0为最大公约数, 以y0为最小公倍数. 试求:满足条件的所有可能的两个正整数的个数.

输入格式

x0,y0

输出格式

满足条件的P,Q的个数

样例

样例输入

3 60

样例输出

4

#include<bits/stdc++.h> using namespace std; long long a,b,o,ans=0; int main(){ scanf("%lld%lld",&a,&b); o=a*b; for(long long i=1;i*i<=o;i++){ if(o%i==0&&__gcd(i,o/i)==a){ if(i*i==o)ans--; ans+=2; } } printf("%lld",ans); return 0; }

例题四：[NOIP2001]最大公约数和最小公倍数问题

题目描述

已知N个数，这N个数的乘积为A,又已知M个数，这M个数的乘积为B。求A,B的最大公约数。如果其最大公约数超过9位，则只需输出最后9位。

输入格式

第一行一个整数N.（1<=N<=1000） 第二行N个整数，均小于1000000000，它们的乘积为A

第三行一个整数M(1<=M<=1000) 第四行M个整数，均小于1000000000，它们的乘积为B

输出格式

一个整数，即A,B的最大公约数。若超过9位，则只输出9位。

样例

样例输入

3 2 3 5 2 4 5

样例输出

10

#include<bits/stdc++.h> using namespace std; long long r[10000005],ans=1,n,m,a,pd; priority_queue<int>q; priority_queue<int>q1; void f(long long x){ for(long long i=2;i*i<=x;i++){ while(x%i==0){ x/=i; q.push(-i); } } if(x>1){ q.push(-x); } } void f1(long long x){ for(long long i=2;i*i<=x;i++){ while(x%i==0){ x/=i; q1.push(-i); } } if(x>1){ q1.push(-x); } } int main(){ scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a); f(a); } scanf("%lld",&m); for(int i=1;i<=m;i++){ scanf("%lld",&a); f1(a); } while(q.size()&&q1.size()){ int x=-q.top(),y=-q1.top(); if(x==y){ if(pd==0&&ans*y>1000000000){ pd=1; } ans=((ans%1000000000)*(y%1000000000))%1000000000; q.pop(); q1.pop(); }else if(x<y){ q.pop(); }else if(x>y){ q1.pop(); } } if(pd)printf(" lld",ans%1000000000); else printf("%lld",ans%1000000000); }