[NOIP2001 普及组] 最大公约数和最小公倍数问题

题目链接[NOIP2001 普及组] 最大公约数和最小公倍数问题 - 洛谷https://www.luogu.com.cn/problem/P1029

---

题目描述

输入两个正整数x0​,y0​，求出满足下列条件的 P, Q的个数：

1. P,Q 是正整数。

2. 要求 P, Q以x0​为最大公约数，以y0​为最小公倍数。

试求：满足条件的所有可能的P,Q的个数。

输入
        一行两个正整数x0​,y0​。

输出

        一行一个数，表示求出满足条件的P, Q的个数。

样例组

输入
3 60

输出 4

---

题目思路

        这是一道水题比较简单的题目。首先输入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;
long long 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;
}

这道题目就这么多(不开O2还是能过的)。

---