倒水問題

   上題。

       題目詳情:

   有兩個容器，容積分別為A升和B升，有無限多的水，現在需要C升水。

   我們還有一個足夠大的水缸，足夠容納C升水。起初它是空的，我們只能往水缸裡倒入水，而不能倒出。

   可以進行的操作是：

1. 把一個容器灌滿；

2. 把一個容器清空容器裡剩余的水全部倒掉，或者倒入水缸）；

3. 用一個容器的水倒入另外一個容器，直到倒出水的容器空或者倒入水的容器滿。

    問是否能夠通過有限次操作，使得水缸最後恰好有C升水。

   輸入：三個整數A, B, C，其中 0 < A , B, C <= 1000000000

   輸出：0或1，表示能否達到要求。

int gcd(int a,int b)
{
    if(a<b)return gcd(b,a);
    if(b==0)return a;
    return gcd(b,a%b); 
}
                                 
                                 
bool can(int a,int b,int c) {
    int m=gcd(a,b);
    if(c%m==0)
        return true;
    else
        return false;
}

int mod(int a,int b)
{
    return b?mod(b, a%b):a; 
}
              
bool can(int a,int b,int c) {
    int res;
    res=mod(a,b);
                
    if(c%res==0)
        return true;
    else
        return false;
}

本文出自 “淡定的dreamer” 博客，請務必保留此出處http://idiotxl1020.blog.51cto.com/6419277/1290279