Cách tiếp cận "ngây thơ"

Ta thấy trong C++ có ~2~ hàm tính Loga cơ bản là log2 cho phép tính ~log_2(x)~ và log cho phép tính ~log_{10}(x)~ và ta có sẵn một công thức: ~log_b(a) = \frac{log_c(a)}{log_c(b)}~ ~(*)~ với ~c~ là một hệ số bất kỳ.

Ở đây C++ cho ta ~2~ hệ số Loga cơ bản ( như đã đề cập ở trước ) là ~2~ và ~10~, ta có thể lấy bất kỳ một trong hai số để áp vào công thức ~(*)~, từ đó ta hoàn toàn có thể tính ~log_a(b^x)~ rồi phân tích kết quả của phép này ra thừa số nguyên tố, nhưng do ~b~ có thể lên tới ~10^{18}~ và ~x~ là ~10^6~ nên có thể bị tràn số khi thực hiện phép ~b^x~.

Cách tiếp cận tối ưu

Để hiểu về lý thuyết chung của phép Loga trong toán, bạn đọc có thể tìm hiểu tại đây.

Ta biết rằng toán học có những phép tính cơ bản nhất là dạng cộng, trừ, nhân và chia. Nhưng để hiểu kĩ hơn về phép tính Loga này thì ta cần phải nắm vững được các phép tính cơ bản, từ đó ta có một số ý nghĩa của phép chia như sau:

1. Phép chia cho biết số lần cần cộng từ số ~A~ để được số ~B~.
2. Phép nhân là cộng nhiều lần thì phép chia là trừ nhiều lần.

Từ cách nhìn đó, ta có thể hiểu tương tự đối với ý nghĩa của phép Loga:

1. Phép Loga cho biết số lần cần nhân từ số ~A~ để được số ~B~.
2. Phép mũ là nhân nhiều lần thì phép Loga là chia nhiều lần.

Nhận xét 1: Ta có dữ kiện từ để bài: ~a~ là một sô nguyên tố và ~a \leq b~, ta xem ~a~ là số chia và ~b~ là số bị chia, từ đó ta có ~2~ trường hợp:

• ~b~ là bội của ~a^y~ ( ~b~ chia hết cho ~a^y~ ) với ~y~ là số nguyên ~( y \geq 1 )~: việc của ta bây giờ chỉ là đếm số lần xuất hiện của ~a~ trong ~b~, tức là số lần ~b~ chia cho ~a~ để được ~1~, số lần xuất hiện này chính là ~y~, đáp án của ta cho phép ~log_a(b)~ là ~y~, khi phân tích ~y~ ra dạng thừa số nguyên tố, ta có ~y = P_1^{W_1} \times P_2^{W_2} \times \dots \times P_l^{W_l}~~(**)~ với: ~P~ là thừa số nguyên tố của ~y~, ~W~ là số mũ của thừa số nguyên tố ~P~, ~l~ là số lượng thừa số nguyên tố của ~y~.

• ~b~ không là bội của ~a^y~ ( ~b~ không chia hết cho ~a^y~ ) với ~y~ là số nguyên ~(y \geq 1)~: rõ ràng số lần xuất hiện của ~a~ trong ~b~ giờ đây sẽ là số thực, ở dạng số thực sẽ không thể biểu diễn dưới dạng thừa số nguyên tố được, nên khi xảy ra trường hợp này ta sẽ in ~-1~.

Nhận xét 2: Nếu như ~log_a(b)~ là đếm số lần xuất hiện của ~a~ trong ~b~, vậy ~log_a(b^x)~ là số lần xuất hiện của ~a~ trong ~b~ được gấp lên ~x~ lần, do đó công thức của đề bài sẽ biến đổi từ ~log_a(b^x)~ về ~x \times log_a(b)~, mà ~log_a(b)~ đã được tính từ ~(**)~, vậy nhiệm vụ còn lại của ta chỉ là phân tích số ~x~ ra dạng thừa số nguyên tố mà thôi, khi phân tích ~x~ ra dạng thừa số nguyên tố, ta có ~x = p_1^{w_1} \times p_2^{w_2} \times \dots \times p_k^{w_k}~ ~(***)~ với: ~p~ là thừa số nguyên tố của ~x~, ~w~ là mũ của thừa số nguyên tố ~p~, ~k~ là số lượng số thừa số nguyên tố của ~x~.

Từ ~(**)~ và ~(***)~, đáp án của bài toán là: ~p_1^{w_1} \times p_2^{w_2} \times \dots \times p_k^{w_k} \times P_1^{W_1} \times P_2^{W_2} \times \dots \times P_l^{W_l}~

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 = 1E5;

bool f[N+9];
int a;
ll b;
int x;
vector<int> prime;
int xRes[N+9];

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

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

void factorize(int x)
{
    for (int i = 0;i < (int)prime.size(); ++i)
    {
        int val = prime[i];
        if (x % val == 0)
        {
            int cntPw = 0;
            while (x % val == 0)
                x /= val, ++cntPw;
            xRes[val] += cntPw;
        }
    }

    if (x > 1) xRes[x] += 1;
}

int findPw(int a,ll b)
{
    int cnt = 0;
    while (b % a == 0)
    {
        b /= a;
        ++cnt;
    }

    if (b > 1) return -1;
return cnt;
}

int main()
{
    fastIO

    sieve();

    int t;
    cin>>t;

    while (t--)
    {
        cin>>a>>b>>x;

        for (int i = 1;i <= N; ++i) xRes[i] = 0;

        try
        {
            int res = findPw(a, b);
            if (res > 0)
            {
                factorize(res);
                factorize(x);
                for (int i = 1;i <= N; ++i) if (xRes[i] > 0) cout<<xRes[i]<<" "; cout<<"\n";
                for (int i = 1;i <= N; ++i) if (xRes[i] > 0) cout<<i<<" ";
                cout<<"\n";
            }
            else throw(res);
        }
        catch(int res)
        {
            cout<<-1<<"\n";
        }
    }
}