题目描述

难度分:$1300$

输入$T(\leq 10)$表示$T$组数据。每组数据输入$n(2 \leq n \leq 10^9)$。

输出两个正整数$a$和$b$，满足$a+b=n$且$LCM(a,b)$尽量小。

输入样例

3
4
6
9

输出样例

2 2
3 3
3 6

算法

分解质因数

如果$a$和$b$中一个数是另一个数的倍数，那么它们两个的最小公倍数就是那个较大的数。这时候我们只需要让那个较小的数尽可能大就好了，直接对$n$分解质因数，找到最小的质因子$factor$，则有$a=\frac{n}{factor}$，$b=n-a$。

否则$n$是一个质数，那最优解就是$a=1$，$b=n-1$。此时两者的最小公倍数为$n-1$，其余情况的$LCM$肯定会更大。

复杂度分析

时间复杂度

先用$Miller$ $Rabin$算法来判断$n$是否是质数，时间复杂度为$O(Tlogn)$，其中$T$是检测轮数，一般情况下就是$7$，因此判质数的时间复杂度为$O(logn)$。如果$n$不是质数需要对$n$做质因数分解找到最小质因子，用$Pollard$ $Rho$算法其期望时间复杂度为$O(n^{\frac{1}{4}}logn)$。

综上，整个算法的时间复杂度为$O(n^{\frac{1}{4}}logn)$，瓶颈在于$Pollard$ $Rho$算法。

空间复杂度

空间瓶颈在于整个过程中存在欧几里得算法求最大公约数，递归深度是$O(logn)$，额外空间复杂度为$O(logn)$。但如果不用递归实现而是迭代实现，那额外空间复杂度就是$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int t, n;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

// Miller-Rabin算法判断质数
LL fast_power(__int128 a, LL k, LL p) {
    LL res = 1 % p;
    while(k) {
        if(k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

bool miller_rabin(LL n) {
    if(n == 2) return true;
    if(n <= 1 || n % 2 == 0) return false;
    LL base[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    LL u = n - 1, k = 0;
    while(!(u&1)) u >>= 1, k++;
    for(auto&x: base) {
        if(x % n == 0) continue;
        LL v = fast_power(x, u, n);
        if(v == 1 || v == n - 1) continue;
        for(int j = 1; j <= k; j++) {
            LL last = v;
            v = (__int128)v * v % n;
            if(v == 1) {
                if(last != n - 1) return false;
                break;
            }
        }
        if(v != 1) return false;
    }
    return true;
}

// Pollard-Rho分解质因数
LL Pollard_Rho(LL n) {
    static mt19937_64 sj(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<LL> u0(1, n - 1);
    LL c = u0(sj);
    auto f = [&](LL x) {
        return ((__int128)x * x + c) % n;
    };
    LL x = f(0), y = f(x);
    while(x != y) {
        LL d = __gcd(abs(x - y), n);
        if(d != 1) return d;
        x = f(x), y = f(f(y));
    }
    return n;
}

void get_factor(LL n, unordered_map<LL, int, custom_hash>& counter) {
    if(n == 1) return;
    if(n == 4) {
        counter[2] += 2;
        return;
    }
    if(miller_rabin(n)) {
        counter[n] += 1;
        return;
    }
    LL x = n;
    while(x == n) x = Pollard_Rho(n);
    get_factor(x, counter);
    get_factor(n/x, counter);
}

int main() {
    scanf("%d", &t);
    unordered_map<int, array<int, 2>> mem;
    while(t--) {
        scanf("%d", &n);
        if(mem.count(n)) {
            printf("%d %d\n", mem[n][0], mem[n][1]);
        }else {
            if(miller_rabin(n)) {
                printf("%d %d\n", 1, n - 1);
                mem[n] = {1, n - 1};
            }else {
                unordered_map<LL, int, custom_hash> counter;
                get_factor(n, counter);
                int ti = counter.begin()->first;
                for(auto&[factor, _]: counter) {
                    if(factor < ti) ti = factor;
                }
                int a = n / ti, b = n - a;
                mem[n] = {a, b};
                printf("%d %d\n", a, b);
            }
        }
    }
    return 0;
}