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

ceshyong

已于 2022-07-28 09:25:13 修改

阅读量545

点赞数 5

分类专栏： CCF 文章标签：算法 c++

于 2022-07-25 16:38:19 首次发布

本文链接：https://blog.csdn.net/ceshyong/article/details/125977513

版权

CCF 专栏收录该内容

8 篇文章

订阅专栏

该博客介绍了如何解决一道编程竞赛题目，该题目要求找到所有满足条件的正整数对(P, Q)，使得P和Q的最大公约数为x0，最小公倍数为y0。博主提供了算法思路，包括判断完全平方数，以及遍历循环查找满足条件的P和Q。最终，通过计算得出满足条件的(P, Q)的个数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

题目描述

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

P,Q 是正整数。
要求 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;
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;
}

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