首页 > 其他分享 >P1029 最大公约数和最小公倍数问题(普及−) 题解

P1029 最大公约数和最小公倍数问题(普及−) 题解

时间:2023-11-25 22:00:49浏览次数:33  
标签:公倍数 题解 最小 int 最大公约数 using include P1029

题目传送门

想要做这题,我们要先了解一下最大公约数

最大公因数,也称最大公约数最大公因子,指两个或多

个整数共有约数中最大的一个。a,b的最大公约数记为

(a,b),同样的,a,b,c的最大公约数记为(a,b,

c),多个整数的最大公约数也有同样的记号。求最大公

约数有多种方法,常见的有质因数分解法、短除法、辗转

相除法、更相减损法。

还有最小公倍数

两个或多个整数公有的倍数叫做它们的公倍数,其中除0

以外最小的一个公倍数就叫做这几个整数的最小公倍数

整数a,b的最小公倍数记为[a,b],同样的,a,b,c的

最小公倍数记为[a,b,c],多个整数的最小公倍数也有

同样的记号。

我才不会告诉你我是抄的百度百科呢!



下面进入正题,因为最大公约数*最小公倍数是等于原数之积的,所以有了下面的式子。

X0乘Y0=P乘Q

所以这道题我们可以用暴力做,下面是代码。

#include <bits/stdc++.h>//万能头 
using namespace std;
int n,m,s;//统计PQ的个数 
int main()
{
	cin>>n>>m;
	for(int i=n;i<=m;i++)
	{
		for(int j=n;j<=m;j++)
		{
			if(__gcd(i,j)==n&&i*j/__gcd(i,j)==m)//__gcd是求最大公约数函数 
			{
				s++;//注意,这里不能加2,因为这里是统计PQ一共有多少组,而不是P和Q一共有多少个 
			} 
		}
	}
	cout<<s;//直接输出 
	return 0;
}

不带注释版[坏笑]

#include <bits/stdc++.F>
using namespace std;
int a,b,s;
int mian()
{
	cin>>n>>m;
	for(int i=n;i<=m;j++)
	{
		for(int j=n;;j++)
		{
			if(__gcd(i,j)==m&&ji*j/__gcd(i,j)==n)
			{
				s+;
			} 
		}
	}
	cout<<s;
	retrun 0;
}

但是暴力还是没有AC,错误有以下两个

  1. Noip比赛中不允许使用__gcd函数

  2. 两个for循环导致TLE

知道了错误,就赶紧改正吧,下面是AC代码

#include<iostream>
using namespace std;
int ans; 
int lcm(int a,int b)//最小公倍数函数 
{
	if(a<b)
	{
		swap(a,b); 
	}
	if(a%b==0)
	{
		return b;//辗转相除法 
	}
	else
	{
		return lcm(b,a%b);
	} 
}
int gcd(int a,int b)//最大公约数函数 
{
	return (a*b/lcm(a,b));// 直接用前面 X0乘Y0=P乘Q的公式求出最大公约数 
}
int main()
{
	int a,b; 
	cin>>a>>b;//输入 
	for(int i=a;i<=b;i++)
	{
		int j=a*b/i; //这就是优化的地方,因为X0乘Y0=P乘Q,所以j可以不用for循环,直接用a*b/i就行了 
		if(lcm(i,j)==a&&gcd(i,j)==b)  //如果用函数算出来i和j的最大公约数和最小公倍数与a,b相等 
		{
			ans++;//标记加1 
		}
	}
	cout<<ans; //输出 
	return 0;
}	

不带注释版[坏笑]

#include<iostream>
using namespace std; 
int ans; 
int lcm(int a,int b)
{
	if(a<b)
	{
		swap(a,b); 
	}
	if(a%b==0)
	{
		return b;
	}
	else
	{
		return lcm(b,a%b);
	} 
}
int gcd(int a,int b)
{
	return (a*b/lcm(a,b));
}
int main()
{
	int a,b; 
	cin>>a>>b;
	while(1)	cout<<"(‘_’)";
	for(int i=a;i<=b;i++)
	{
		int j=a*b/i;
		if(lcm(i,j)==a&&gcd(i,j)==b)
		{
			ans++;
		}
	}
	cout<<ans;
	return 0;
}	

标签:公倍数,题解,最小,int,最大公约数,using,include,P1029
From: https://www.cnblogs.com/BadBadBad/p/P1029.html

相关文章

  • Win10无法访问linux上的samba服务问题解决
    转自https://blog.csdn.net/u014635079/article/details/124703840服务端:Ubuntu20.04, samba版本4.13.17-Ubuntu客户端:Win10 问题1:按照教程搭建好samba服务之后,从windows可以ping通linux的情况下,从windows端无法连接samba服务器。 解决:通过打开Lanman工作站的启用不......
  • P8543 「Wdoi-2」纯粹的复仇女神 题解
    自己的套路还是见少了。思路考虑扫描线。每一个颜色的\(\min\)具有单调性,这个很好看出来。可以使用一个单调栈来维护。这里都是朴素的。考虑如何维护。我们发现在通过单调栈维护的时候。需要支持撤销上一个元素对区间的影响。我就在这里卡了很久。我们有一个很暴力的......
  • 14:苏格拉底问答、实践过程截图、遇到问题解决问题截图,代码链接、
    ......
  • 苏格拉底问答、实践过程截图、遇到问题解决问题截图,代码链接
    include<stdio.h>include<stdlib.h>include<sys/types.h>include<sys/socket.h>include<netinet/in.h>include<arpa/inet.h>include<time.h>include<string.h>include<unistd.h>defineMAXLINE256......
  • 两道题解决滑动窗口问题
    定长567.字符串的排列-力扣(LeetCode)给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。换句话说,s1 的排列之一是 s2 的 子串 。解题思路1°传统套路就是定义两个哈希表,一个存储s1中每个字符的出现次数,记s1......
  • P1002题解
    思路设\(dp_{i,j}\)表示第\(i\)行\(j\)列卒走到这里有多少种方式。卒是可以向右和下走,所以到这个点只能从左或上来,不难得出转移公式:\(dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}\)。如果马在这个点上或者说马能到这个点上,那么卒不能到这个点,也就是卒到这个点的方式为\(0\)。如......
  • P1135题解
    思路我写的好像是动规的做法。设\(f_{i,j}\)表示第\(i\)步\(j\)个点是否可以走到,值要么为\(1\),要么为\(0\)。最多走\(n\)步,因为总共只有\(n\)个点,每一步都肯定会多延伸出一个点,要不然就重复计算。不难得出转移公式:\(f_{i+1,j+k_j}=f_{i,j}\)\(f_{i+1,j-k_j}=f_{......
  • P1003题解
    简单模拟题。思路枚举每一个地毯,因为后面的会覆盖前面的,所以从正序枚举。如果要求的点的坐标在当前地毯上,则将答案赋值为当前地毯编号。最后输出答案。那如果这个点没有地毯呢?答案初始设为\(-1\),这样没有地毯覆盖的话,答案不会改变,这样输出答案就会是\(-1\)。注意:记得赋初......
  • SP9199题解
    考察了小学奥数知识,不会的请先去学习一下相遇与追及。思路两个人相遇的点一定是有周期性的,我们可以先算出一个周期会走多远,而这个距离是两人速度的最小公倍数。接着需分情况讨论。如果两人是同向,则为追及,需用距离除以一人的速度减去距离除以另一人的速度。需要取绝对值。......
  • 求四个数的最小公倍数
    #include<stdio.h>longintfact(longintx,longinty){ inti,j;  for(i=1;i<=x*y;i++) {  if(x%y==0||y%x==0)  {  returnx>y?y:x;  break;  }    j=x*i;  if(j%y==0)  {  returnj;......