程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1722 Cake （GCD）

HDU 1722 Cake （GCD）

編輯：C++入門知識

HDU 1722 Cake （GCD）

Cake

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2609 Accepted Submission(s): 1253 Problem Description 一次生日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塊。

Author LL Source HZIEE 2007 Programming Contest

解題思路：先份成p塊，然後再拼到一起，再從原來開始的地方，將蛋糕再分成q份，中間肯定會出現完全重合的塊數為k，則此是需要分的塊數就是 p + q - k.

現在只需要求出k即可，其實k是什麼呢，就是GCD（p，q），就是p和q的最大公約數。

AC代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x7fffffff

int gcd(int a, int b){
    return !b ? a : gcd(b, a%b);
}

int main()
{
    #ifdef sxk
        freopen("in.txt","r",stdin);
    #endif
    int p, q;
    while(scanf("%d%d",&p, &q)!=EOF)
    {
        printf("%d\n", p + q - gcd(p, q));
    }
    return 0;
}