Как получить номера из данных GCD и LCM

Question

Я пытаюсь решить следующую проблему. Поиск чисел (два) в форме GCD и LCM (не обязательно правильно) Если данные GCD и LCM верны, мне нужно найти соответствующие два числа из них. В противном случае GCD и LCM не верны, и, конечно, не существует соответствующих номеров.

Вот как я пытаюсь подойти. И это не правильное решение. Как я должен подходить к этому правильно. [Примечание: не стесняйтесь комментировать на любом языке программирования или дайте мне знать алгоритм]

public class GCD_LCM {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a,b;
        a = scan.nextInt();
        b = scan.nextInt();

        int number = num(a,b);
        if(number==-1){
            System.out.println(number);
        }else {
            int fn =number;
            int sn =(a*b)/fn;
            System.out.println(fn+" "+sn);

        }
    }

    private static int num (int gcd, int lcm){
        int a =0;
        if(lcm>=gcd*2){
            for(int i =2; i<lcm/2; i++){
                if(lcm%i ==0){
                     a = lcm/i;
                }
            }
            return a;
        }
        return -1;
    }
}

Answer 1

import java.util.Scanner;

public class GCD_LCM {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int a, b;
        a = scan.nextInt();
        b = scan.nextInt();

        int number = num(a, b);
        if (number == -1) {
            System.out.println(number);
        } else {
            int fn = number;
            int sn = (a * b) / fn;
            System.out.println(fn + " " + sn);
        }
    }

    static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        return gcd(b%a , a);
    }

    private static int num(int gcd, int lcm) {
            int p = gcd * lcm;
            for (int a = 2; a <=lcm; a++) {
                if ((p%a == 0) && gcd(a, p/a) == gcd)
                    return a;
                }
                return -1;
        }

}

Пока это решение верное. Единственная проблема - «превышение лимита времени». Как это оптимизировать. Спасибо @Ayda за твою идею. Это поможет мне улучшить мое решение

Answer 2

Часто нет однозначного ответа на проблему. Например, если GCD = 1 и LCM = 6, возможные ответы включают A = 2, B = 3 и A = 1, B = 6. Если вам нужен только один возможный ответ, просто используйте A = GCD и B = LCM с кодом ошибки, если GCD не делит LCM.

Вот код на Python 3. Я оставлю преобразование входных данных в целые числа для вас.

def gcd_lcm(gcd, lcm):
    """Print two possible numbers given their GCD (Greatest 
    Common Divisor) and LCM (Least Common Multiple).
    If that is not possible, print -1."""
    if lcm % gcd == 0:
        print(gcd, lcm)
    else
        print(-1)

Answer 3

Алгоритм:

p = G*L
count = 0
for a = 1 to L
    if p%a == 0 and gcd(a, p/a) = G
        count++
    end if
end for
return count

    public class GCD
    {
        // Java function to calculate GCD
        // of two numbers
        static int gcd(int a, int b)
        {
            if (a == 0)
                return b;
            return gcd(b%a , a);
        }

        // Java function to count number 
        // of pairs with given GCD and LCM
        static int countPairs(int G, int L)
        {
            // To store count
            int count = 0;

            // To store product a*b = G*L
            int p = G*L;

            // p/a will be b if a divides p
            for (int a = 1; a<=L; a++)
                if ((p%a == 0) && gcd(a, p/a) == G)
                    count++;

           return count;
        }

        public static void main (String[] args)
        {
            int G = 2, L = 12;
            System.out.print("Total possible pair with GCD " + G);
            System.out.print(" & LCM " + L);
            System.out.print(" = " + countPairs(G, L));

        }

    }