This program is for UVA 10193 All You Need Is Love

UVA 10193 All You Need Is Love.cpp

//This program is for UVA 10193 All You Need Is Love
//http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1134

/*
S is made of Love when "S can be divisible by L." (with no remainder)
When (S1%L == 0 && S2%L == 0), we have "All you need is love!"
otherwise, we get "Love is not all you need!"

we want "(S1%L == 0 && S2%L == 0)" is true.
So we have to find a L, which is Common Divisor of S1 and S2.
And this L is not 1 !
*/

#include<stdio.h>
#include<string.h>

// convert a binary number to decimal
int binaryToDecimal(char a[])
{
 
    int len = strlen(a);
    int m =0;
 
    m = a[0] - '0';// change the character to integer
    for(int i = 1; i < len; i++)
    {
        m *= 2;      
        m += a[i] - '0';// change the character to integer
    }
 
    //printf("str: %s  m: %d\n", a, m);// for check
    return m;
}

/* find the Greatest Common Divisor
The parameter a must be bigger than b!
use the recursive to find GCD.
*/
int GCD(int a, int b)
{
    if(b > a)
        return GCD(b, a);
     
    if(b == 0)
        return a;
    else
        return GCD(b, a%b);
}

int main()
{
    int n, x, y, gcd;
    char s1[32], s2[32];
 
    scanf("%d\n", &n);
 
    for(int t = 1; t <= n; t++)
    {
        gets(s1);
        gets(s2);
     
        x = binaryToDecimal(s1);
        y = binaryToDecimal(s2);
     
        gcd = GCD(x, y);
     
        if(gcd != 1)
            printf("Pair #%d: All you need is love!\n", t);
        else
            printf("Pair #%d: Love is not all you need!\n", t);
    }
 
    return 0;
}