HDU1722 Cake HDU2504 又见DCG HDU1108最小公倍数.

151 阅读 0 评论 100 点赞

我是靠谱客的博主直率饼干，这篇文章主要介绍HDU1722 Cake HDU2504 又见DCG HDU1108最小公倍数.，现在分享给大家，希望可以做个参考。

这些题都是与最大公约数也就是最大公因数有关系的。对于求最大公约数的函数有很多这里推荐一个代码数目少的代码。

复制代码

1
2
3
4
int gcd(int a, int b)
{
    return b ? gcd(b,gcd( a % b )) : a
}

一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕.问最少要将蛋糕切成多少块(每块大小不一定相等),才能使p人或者q人出席的任何一种情况,都能平均将蛋糕分食.

Input

每行有两个数p和q.

Output

输出最少要将蛋糕切成多少块.

Sample Input

复制代码

1
2 3

Sample Output

复制代码

1
2
4

Hint

复制代码

1
2
3
将蛋糕切成大小分别为1/3,1/3,1/6,1/6的四块即满足要求.
当2个人来时，每人可以吃1/3+1/6=1/2 , 1/2块。
当3个人来时，每人可以吃1/6+1/6=1/3 , 1/3, 1/3块。

对于这一题的思路大致为，一个蛋糕可以先分割成p块然后再将其合成完整的一个蛋糕，然后再次分割成q块，总计是p+q块，但是有重叠的蛋糕重叠的蛋糕的块数就是p和q的最大公约数比如题中的2 3的最大公约数就是1 所以答案为4

先套模板然后编写函数。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h> 
using namespace std;
int gcd(int a,int b)
 {
    return b ? gcd (b, a % b) : a;
} 
int main()
{
	int p,q,k;
	while(scanf("%d%d",&p,&q)!=EOF)
	{
	k=gcd(p,q);
	printf("%dn",p+q-k);
}
}

又见GCD

有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a和c的最大公约数为b，现已知a和b，求满足条件的最小的c。

Input

第一行输入一个n，表示有n组测试数据，接下来的n行，每行输入两个正整数a,b。

Output

输出对应的c，每组测试数据占一行。

Sample Input

复制代码

Sample Output

复制代码

这个题进行暴力解法要首先明白c是b的倍数然后c不等于0且c不等于b 因此c应该从2*b开始每次加b；进行循环一直算出来对应的最大公约数等于b然后返回这个值。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h> 
using namespace std;
int gcd(int a, int b)
 {
 	return b ? gcd (b, a % b) : a;
}
int main()
{
	int n,a,b,c;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d",&a,&b);
		for(c=b+b;c<=a;c+=b)
		{
			if(gcd(a,c)==b)
			{
				break;
			}
		}
		printf("%dn",c);
	}
}

最小公倍数

给定两个正整数，计算这两个数的最小公倍数。

Input

输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数.

Output

对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。

Sample Input

复制代码

1
10 14

Sample Output

复制代码

1
70

这一题依旧是与最大公约数相关联的，有一个公式是

lcm(a,b) *gcd(a,b)= |a·b|

；两个数的积等于最大公约数乘以最小公倍数。

因此还是先模板求出最大公约数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int zhanzhuan(int a,int b)
{
	return b==0? a:zhanzhuan(b,a%b);
}
int main()
{
	int a,b,k;
	while(scanf("%d%d",&a,&b)!=EOF)
	{
		k=zhanzhuan(a,b);
		printf("%dn",a*b/k);
	}