(UVA) 10193 - All You Need Is Love - Solução

- A princípio, tentei como solução algo como:
            boolean achei = false;
            for (int j = 2; j < menor && !achei; j++) {
                if (s1Decimal%j == 0 && s2Decimal%j == 0) {
                    achei = true;
                }
            }
- No entanto, embora a solução esteja correta, houve "Time limit exceeded".

- Como solução, tentei encontrar o MDC (Máximo Divisor Comum). O MDC sendo 1, significa que os números são primos entre si e que, desta forma, a condição desejada não existe.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {

        Main processando = new Main();
        processando.processa();

        System.exit(0);
    }

    static int leitor(BufferedReader br) throws NumberFormatException, IOException {
        int n;
        int resp = 0;
        while (true) {
            n = br.read();
            if (n >= '0' && n <= '9') break;
        }
        while (true) {
            resp = resp*10 + n-'0';
            n = br.read();
            if (n < '0' || n > '9') break;
        }
       
        return resp;
    }

    void processa() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int qteCasos = leitor(br);
       
        for (int i = 0; i < qteCasos; i++) {
            String s1 = br.readLine();
            String s2 = br.readLine();
           
            int s1Decimal = Integer.parseInt(s1, 2);
            int s2Decimal = Integer.parseInt(s2, 2);
           
            int menor = Math.min(s1Decimal, s2Decimal);
            int maior = Math.max(s1Decimal, s2Decimal);
           
            /* Calculando mdc - ao final, o mdc seria o 'maior' */
            int resto = 10000;
            while(resto > 0) {
                resto = maior%menor;
               
                maior = menor;
                menor = resto;
            }
           
            if (maior > 1) {
                bw.write("Pair #" + (i+1) + ": All you need is love!\n");
            }
            else {
                bw.write("Pair #" + (i+1) + ": Love is not all you need!\n");
            }
        }
       
        bw.flush();
        bw.close();
       
        return;
    }
}