辗转相除法，如果余数为0就返回较小数，否则继续除： 求54与36的最大公约数 而且任意两个数的最大公约数乘以最小公倍数的积等于这两个数的积 例如 AC代码：

#include<stdio.h> #include<math.h> int ojld(int i,int j) { if(i0)return j; ojld(j%i,i); } int main() { int x,y,q,num=0,k; int i; scanf("%d%d",&x,&y); k=x*y; q=sqrt(k); for(i=x;i<=q;i++) { if(k%i0&&ojld(i,k/i)==x) num++; } printf("%d\n",num*2); return 0; }

最大公约数和最小公倍数的乘积就是原两个数的积

空降坐标：CP002768 来源：NOIP2001 普及组 请看代码

这是一道水题比较简单的题目。首先输入x0 ,y0 。然后将x0,y0相乘存入一个变量R中。然后判断R是否为完全平方数(为一个数的平方)，如果是则答案变量ans--；然后开一重循环从1循环到根号R，判断R是否能被循环变量i整除而且i与R/i的最大公因数是x0(只要求出一个即可)，若符合条件则ans+=2; 最后输出ans即可。(注意这些变量都需要开long long) 至于最大公因数，可以直接使用系统函数库里的__gcd，或者专门写一个gcd函数： 这道题目的主程序如下： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ AC代码 欢迎加入团队

#include <bits/stdc++.h> using namespace std; long long x,y; long long gcd(long long a,long long b) { return b? gcd(b,a%b):a; } bool vis[100005]={0}; long long lcm(int a,int b) { return ab/gcd(a,b); } int main() { cin>>x>>y; long long i,j; long long z=xy; long long ans=0; for(i=x;i<=y;i++)//i是a { if(z%i==0) { if(gcd(i,z/i)x&&lcm(i,z/i)y) { if(iz/i) { cout<<ans2+1; return 0; } if(vis[i]) { cout<<ans2; return 0; } else { ans++; vis[i]=vis[z/i]=1; } } } } if(ans0)cout<<0; return 0; }

注：此题解仅萌新专用，想直接看代码的往下翻 A78.最大公约数和最小公倍数问题 题目描述 输入两个正整数x0,y0,求出满足下列条件的 P,Q 的个数： P,Q 是正整数。 要求 P,Q 以 x0为最大公约数，以 y0 为最小公倍数。 试求：满足条件的所有可能的 P, Q 的个数。 先输入 或者 这不用我多说了吧 开始枚举 取值范围是x~y。因为p和q的最大公约数不会大于p或者q，最小公倍数也不会小于p或者q。 条件 先加一个计数变量 使用c++自带的函数求出做大公约数和最小公倍数 输出 无需多讲 AC代码如下：

1.获取输入 2.切分输入 3.获取两个数的乘积t 4.循环遍历