最大公约数和最小公倍数问题 题解

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

#define ll long long
ll gcd(ll a,ll b)//与__gcd等价 
{return (b==0?a:gcd(b,a%b));}//三元运算符

这道题目的主程序如下：

int getans(int n,int m)
{
	int r=n*m,ans=0;
	if(n==m) ans--; 
	for(int i=1;i*i<=r;i++)//这样写比使用sqrt(r)更快
		if(n%i==0&&gcd(i,n/i)==m) ans+=2;//这里也可以直接使用__gcd
	return ans;	 
}

---

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll m,n,k,ans;
ll gcd(ll a,ll b)//与__gcd等价 
{return (b==0?a:gcd(b,a%b));}
int main()
{
	cin>>m>>n;k=n*m;
	if(n==m) ans--;
	for(ll i=1;i*i<=k;i++)
		if(k%i==0&&gcd(i,k/i)==m) ans+=2;//这里也可以直接使用__gcd
	cout<<ans;
	return 0;
}

欢迎加入团队