Nhận xét:

• Với ~LCM(LCM(x, y),a) = T~ thì ~x, y~ và ~a~ đều là ước của ~T~.
• Với ~A~ là một ước của ~T~, ~LCM(T,A) = T~.

Nếu ~a~ thỏa mãn là ước của ~T~, ta quy về bài toán tìm ~x, y~ là ước của ~T~ sao cho ~LCM(x,y) = T~ và ~1 < x,y < T~.

Giả sử có cặp ~x, y~ thỏa mãn thì sau khi phân tích ~x, y~ và ~T~ ra các thừa số nguyên tố, sẽ có ít nhất một thừa số nguyên tố có bậc của ~x~ bằng bậc của ~T~, thừa số đó ở ~y~ sẽ có bậc bé hơn của ~T~ và cũng có ít nhất một thừa số nguyên tố có bậc ở ~y~ bằng ~T~, có bậc của ~x~ bé hơn.

Đơn giản hóa, ~T~ có dạng ~T = P^k \times T'~, với ~T'~ là 1 ước của ~T~, ~P~ là một số nguyên tố, ~k~ lớn nhất có thể và ~k > 0~.

Ta tìm và gán ~x = P^k~, ~y = T / x~. Nếu ~y = 1~ tức là ~T~ là lũy thừa của một số nguyên tố, khi đó không tồn tại thừa số nguyên tố thứ hai cấu tạo lên ~T~.

Trong trường hợp không tồn tại thừa số nguyên tố thứ hai cấu tạo lên ~T~ hoặc ~T~ không chia hết cho ~a~, ta chắc chắn không tìm được cặp ~x, y~ thỏa mãn và in ra ~-1~. Việc tìm ~P~ ở đây rất đơn giản vì ~P \le sqrt(T)~ hoặc ~P = T~ (nếu ~T~ là số nguyên tố).

Độ phức tạp: ~O(sqrt(T))~.

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 1E6;

bool f[N+9];
vector<int> prime;
int pwA[N+9], pwT[N+9];
vector<int> numT, numA;
int a, T;

void sieve()
{
    f[1] = f[0] = 1;
    for (int i = 2;i <= trunc(sqrt(N)); ++i)
        if (f[i] == 0)
            for (int j = i*i;j <= N; j += i)
                f[j] = 1;

    for (int i = 2;i <= N; ++i)
        if (f[i] == 0) prime.push_back(i);
}

void factorize(int targetNum, vector<int> &listFact, int pw[N])
{
    for (int i = 0;i < (int)prime.size(); ++i)
    {
        int fact = prime[i];
        while (targetNum % fact == 0)
        {
            targetNum /= fact;
            if ((int)listFact.size() == 0 || listFact.back() != fact) listFact.push_back(fact);
            ++pw[fact];
        }
    }

    if (targetNum > 1)
    {
        listFact.push_back(targetNum);
        ++pw[targetNum];
    }
}

ll myPow(ll x, ll y)
{
    ll res = 1;
    while (y > 0)
    {
        if (y & 1) res = res * x;
        y = y >> 1;
        x = x * x;
    }
return res;
}

int myLCM(int x, int y)
{
    return x / __gcd(x,y) * y;
}

int main()
{
    if (fopen(name".INP","r"))
        freopen(name".INP","r",stdin),
        freopen(name".OUT","w",stdout);

    fastIO

    cin>>a>>T;

    sieve();
    factorize(a, numA, pwA);
    factorize(T, numT, pwT);

    vector<int> newT;
    for (int i = 0;i < (int)numT.size(); ++i)
    {
        int fact = numT[i];
        if (pwT[fact] > 0) newT.push_back(fact);
    }

    if ((int)newT.size() <= 1) return cout<<-1, 0;

    int x = 0, y = 0;
    if ((int)newT.size() >= 2)
    {
        int fact = newT[0];
        int pw = pwT[fact];
        x = myPow(fact, pw);

        fact = 0;
        pw = 0;
        ll res = 1;
        for (int i = 1;i < (int)newT.size(); ++i)
        {
            fact = newT[i];
            pw = pwT[fact];
            res *= myPow(fact, pw);
        }

        y = res;
    }

    if (myLCM(a,myLCM(x,y)) == T) return cout<<x<<" "<<y, 0;

    return cout<<-1, 0;
}