Есть ли лучшее решение для этой проблемы LCM?

Question

• Предположим, нам дано число N, которое является положительным целым числом 2 <= N <= 10^9.

• Нам нужно найти два целых числа A и B так, что - (A+B) = N, and LCM(A,B) is Minimum possible.

• Например, если N = 9 then A = 3, B = 6 - единственные действительные ответы.

Что я думал До сих пор

• Если N is even, то A,B будет N/2.
• Если N нечетное, то A,B будет таким, что A is a perfect factor of B and A+B = N.

Что мне нужно знать

• Am i doing right ?
• Did i miss something ?
• Is there any better solution for this ?

Answer 1

Поиск A, B с наименьшим НОК аналогичен поиску A, B с наибольшим НОД. Наибольший возможный НОД - это наибольший множитель N (за исключением самого N).

Итак, если K является наибольшим множителем N, то A = K, B = K * (N / K-1) равно единице. решения. Все решения имеют вид A = jK, B = K (N / Kj), где 1 <= j <N / K. </p>

Вы можете найти наибольший множитель N во времени sqrt (N) по найти наименьшее i в [2, sqrt (N)], которое делит N; тогда наибольший множитель равен N / i.

Например, наибольший множитель 9 (исключая саму 9) равен 3, поэтому A = 3, B = 3 * (3-1) = 6.

Answer 2

Я верю в простую математику.

Указанные вами подсказки были очень важны.

Случай 1:

Если N четное = > A = N / 2, B = N / 2

Случай 2:

Если N простое число => A = 1, B = N-1;

Случай 3:

Если N нечетное => Это сложно.

Теперь, если A + B = N, максимальное возможное значение A (учитывая A <= B) равно <code>N/2.

Кроме того, чтобы минимизировать НОК A и B, LCM(A, B) = max(A, B) = B .... eq (1)

A + B = N .... eq (2)

B = d * A, где d - любое положительное целое число (из уравнения (1)) .... eq (3)

Подставляя уравнение (3) в уравнение (2), мы получаем,

A + d * A = N

A (1 + d) = N

A = N / (d + 1) .... eq (4)

Теперь цель состоит в том, чтобы минимизировать LCM =>, который, в свою очередь, должен минимизировать max (A, B) = B

Если мы хотим минимизировать B, нам нужно максимизировать A (из уравнения (4))

Чтобы максимизировать A, нам нужно минимизировать (d + 1).

Следовательно, (d+1) = D = smallest factor of N, где (D)> = 3 и d = D-1.

Окончательный ответ, A = N / (d + 1) и B = d * A

Взгляните на следующую реализацию, которая имеет Принято приговор по Codeforces:

#include <iostream>
#include <string>
#include <cmath>

typedef long long int LL;

bool isPrime(LL n)
{
    for(LL i = 2 ; i <= sqrt(n) ; i++ )
        if(n%i==0)return false;
    return true;
}


int main()
{
    int t;
    std::cin >> t; 

    while(t--){
        
        LL n, A, B;
        std::cin>>n;

        if( n % 2LL == 0 ) { 
            A = n/2LL ;
            B = n/2LL ; 
        }
        else if(isPrime(n)) {
            A = 1LL ;
            B = n-1LL ; 
        }
        else{
            
            LL D;
            for(LL i = 3; i <= sqrt(n) ; i++ )
            {
                if( n % i == 0) { 
                    D = i; 
                    break; 
                }
            }
            LL d = D - 1LL;
            A = n/(d+1LL);
            B = d*A;
        }

        std::cout<<A<<" "<<B<<std::endl;
    }
    return 0;
}

Answer 3

Использование вышеприведенного подхода @Paul Hankin наконец-то принял решение, большое вам спасибо.

Решение C ++ 14.

ll n,A,B; cin >> n; // long long
        if( n % 2 == 0 ) { A = n/2 ; B = n/2 ; }
        else if(isprime(n)) { A = 1 ; B = n-1 ; }
        else
        {
            ll K;
            for(ll i = 3; i <= sqrt(n) ; i++ )
            {
                if( n % i == 0) { K = n/i ; break; }
            }
            A = K, B = n-K;
        }

Используется функция первичной проверки в программе выше

bool isprime(ll n)
{
    for( ll i = 2 ; i <= sqrt(n) ; i++ )
        if(n%i==0)return false;
    return true;
}