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

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

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

2 3

Sample Output

4

Hint

将蛋糕切成大小分别为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

先套模板 然后编写函数。

#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

2
6 2
12 4

Sample Output

4
8

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

#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

10 14

Sample Output

70

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

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

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

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

​#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);
	}


​

这三道题大致的思路都差不多  全部都是跟最大公约数有相关联的因此要记住最大用约数的算法。

最后

以上就是直率饼干为你收集整理的HDU1722 Cake HDU2504 又见DCG HDU1108最小公倍数.的全部内容，希望文章能够帮你解决HDU1722 Cake HDU2504 又见DCG HDU1108最小公倍数.所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。