整数因子分解问题分治n>=200000000

对于这个问题，我们可以使用Pollard-Rho算法来解决。这个算法是一种基于随机化的算法，可以在多项式时间内完成因子分解。

具体来说，我们可以使用一个随机函数$f(x)$来生成一系列数列$x_0,x_1,x_2,\ldots$。每次通过计算$f(x_i)$得到下一个数$x_{i+1}$，然后计算$x_{i+1}$与$x_i$的最大公因数，如果找到了非1且不同于n的因子，那么我们就成功完成了因子分解。

具体的实现方法可以参考以下代码，其中rand()函数可以用C++的标准库函数来实现，例如使用srand(time(NULL))和rand()来生成随机数。

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long pollard_rho(long long n) {
    long long x = rand() % n, y = x, c = rand() % n, u = 1, v, t = 0;
    for (int lim = 1; lim; ) {
        x = y;
        for (int i = 1; i <= lim; ++i) {
            y = (y * y + c) % n;
            v = u * abs(y - x) % n;
            if (v == 0) return gcd(abs(x - y) / lim, n);
            if (++t == lim) u = v, lim <<= 1, t = 0;
        }
    }
    return n;
}

void factorize(long long n, vector<long long>& factors) {
    if (n == 1) return;
    if (n % 2 == 0) {
        factors.push_back(2);
        factorize(n / 2, factors);
        return;
    }
    if (n % 3 == 0) {
        factors.push_back(3);
        factorize(n / 3, factors);
        return;
    }
    if (n % 5 == 0) {
        factors.push_back(5);
        factorize(n / 5, factors);
        return;
    }
    if (n % 7 == 0) {
        factors.push_back(7);
        factorize(n / 7, factors);
        return;
    }
    if (n % 11 == 0) {
        factors.push_back(11);
        factorize(n / 11, factors);
        return;
    }
    if (n % 13 == 0) {
        factors.push_back(13);
        factorize(n / 13, factors);
        return;
    }
    if (n % 17 == 0) {
        factors.push_back(17);
        factorize(n / 17, factors);
        return;
    }
    if (n % 19 == 0) {
        factors.push_back(19);
        factorize(n / 19, factors);
        return;
    }
    if (n < 100000000) {
        for (int i = 23; i * i <= n; i += 2) {
            if (n % i == 0) {
                factors.push_back(i);
                factorize(n / i, factors);
                return;
            }
        }
        factors.push_back(n);
        return;
    }
    long long d = n;
    while (d == n) d = pollard_rho(n);
    factorize(d, factors);
    factorize(n / d, factors);
}

int main() {
    long long n = 200000000;
    vector<long long> factors;
    factorize(n, factors);
    sort(factors.begin(), factors.end());
    for (int i = 0; i < (int)factors.size(); ++i) {
        cout << factors[i] << " ";
    }
    cout << endl;
    return 0;
}

在上述代码中，我们首先判断n是否是2、3、5、7、11、13、17、19中的一个，如果是，就直接将其作为因子加入结果中；否则，我们就调用pollard_rho函数来寻找n的一个因子d，然后递归地对d和n/d进行因子分解。在pollard_rho函数中，我们使用了Floyd判圈算法来寻找因子，这个算法的时间复杂度是O(sqrt(n))，因此总体时间复杂度是O(sqrt(n)logn)，可以满足n>=200000000的要求。