Tìm tập con có số lượng phần tử lớn nhất sao cho GCD của tập này lớn hơn 1

[tntxtnt]

còn nữa nè =] 2520 với 240 có gcd = 120, 2520 / 120 = 21, 240/120 = 2, gcd(120,21) = 3, gcd(120,2) = 2 đâu phải lúc nào cũng có 1 cái gcd = 1 đâu =]

chạy thử mấy test:
{{240, 2016, 2048}, 3},
{{288, 2520, 4096}, 3},
{{240, 2520, 4096}, 3},
{{180, 1188, 1287}, 3},
{{180, 1188, 1287, 2048, 4096}, 4},
mà debug chỗ này nó hiện bug ra chỗ khác =] thôi phân tích thừa số nt luôn cho rồi =]

[rogp10]

Đành vậy, không cách gì lấy ra power prime được

SQUFOF thực ra nhanh hơn trong khoảng này nhưng Rho dễ viết hơn nhiều lần.

• SQUFOF: O(n^(1/4))
• Rho: O(d^(1/2)) với d là ước số của n.

[tntxtnt]

https://rextester.com/MVOGDP90552

#include <iostream>
#include <cstdint>
#include <set>
#include <cmath>
#include <chrono>
#include <vector>

std::set<int64_t> primeFactors(int64_t);

int main() {
    int64_t numbers[] = {
        967'258'918'703'132'761LL,
        867'538'461'530'699'351LL,
        871'635'412'261'944'677LL,
        980'424'556'411'492'303LL,
        709'636'932'598'957'339LL,
        838'437'935'456'937'481LL,
        928'543'595'321'610'997LL,
        768'600'079'623'327'937LL,
        777'768'294'375'510'029LL,
        844'589'091'915'879'839LL,
        1234567891LL * 1234567891LL,
        2LL * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47,
    };
    std::vector<int64_t> primes;
    auto start = std::chrono::steady_clock::now();
    for (auto n : numbers)
        for (auto p : primeFactors(n)) primes.push_back(p);
    std::chrono::duration<double, std::milli> elapsed =
        std::chrono::steady_clock::now() - start;
    for (auto p : primes) std::cout << p << " ";
    std::cout << "\n" << elapsed.count() << "ms\n";
}


// compute a^d mod n
int64_t modPow(int64_t a, int64_t d, int64_t n) {
    int64_t ret = 1;
    int64_t apow = a;
    for (; d; d >>= 1) {
        if (d % 2) ret = __int128(ret) * apow % n;
        apow = __int128(apow) * apow % n;
    }
    return ret;
}

bool witness(int64_t a, int64_t n, int64_t d, int64_t r) {
    auto x = modPow(a, d, n);
    if (x == 1 || x == n - 1) return true;
    for (auto i = r - 1; i-- > 0;) {
        x = modPow(x, 2, n);
        if (x == 1) return false;
        if (x == n - 1) return true;
    }
    return false;
}

bool isPrimeDetMillerRabin(int64_t n) {
    int64_t d, r; // n-1 = d * 2^r
    for (d = n - 1, r = 0; d % 2 == 0; d >>= 1, r++) {}
    const int64_t arr[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    for (auto a : arr)
        if (!witness(a, n, d, r)) return false;
    return true;
}

template <class T>
T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}

int64_t pollardsRho(int64_t n) {
    auto g = [n](int64_t x) { return (int64_t)((__int128(x) * x + 1) % n); };
    int64_t x = 2, y = 2, d = 1;
    while (d == 1) {
        x = g(x);
        y = g(g(y));
        d = gcd(x > y ? x - y : y - x, n);
    }
    // if (d == n) throw "Failture";
    return d;
}

std::set<int64_t> primeFactors(int64_t n) {
    std::set<int64_t> result;
    // 2
    if (n % 2 == 0) result.insert(2);
    while (n % 2 == 0) n /= 2;
    // odds
    const int iMax = 31623;
    for (int sqrtn = (int)sqrt(n), i = 3; i < sqrtn && i < iMax; i += 2) {
        if (n % i == 0) result.insert(i);
        while (n % i == 0) n /= i;
        sqrtn = (int)sqrt(n);
    }
    while (n > 1) {
        // MR
        if (isPrimeDetMillerRabin(n)) {
            result.insert(n);
            break;
        } else {
            // Pollard's rho
            auto d = pollardsRho(n);
            result.insert(d);
            n /= d;
        }
    }
    return result;
}

12 số 60-bit trong vòng ~ 42ms, 1 số chắc cũng 4ms, 1000 số ~ 4s ko qua khỏi =]

https://www.forthgo.com/blog/2008/10/19/fast-factoring-for-64-bit-integers/
400k số 64-bit ngẫu nhiên mất 811 giây cũng 2ms 1 số :V :V

python nó ~10 giây bên dưới nó là code C vậy chắc cũng lẹ hết mức rồi :V

[rogp10]

vỗ lên trán

Có lẽ là chỉ cần tính n(n-1)/2 cặp gcd, với mỗi số ta đếm số số nguyên tố cùng nhau với nó, rồi lấy N trừ đi là ra kết quả.

[tntxtnt]

    std::mt19937 prbg{(unsigned int)time(0)};
    start = std::chrono::steady_clock::now();
    std::unordered_map<int64_t, int> freq;
    for (int i = 0; i < 1000; ++i) {
        int64_t n = std::uniform_int_distribution<int64_t>{
            2LL, 1'000'000'000'000'000'000}(prbg);
        for (auto p : primeFactors(n)) freq[p]++;
    }
    int result = std::max_element(begin(freq), end(freq), [](auto& a, auto& b) {
                     return a.second < b.second;
                 })->second;
    elapsed = std::chrono::steady_clock::now() - start;
    std::cout << result << "\n" << elapsed.count() << "ms\n";

https://rextester.com/RZD14201
chạy 1000 số ngẫu nhiên mất ~600ms thôi =]

[tntxtnt]

vậy giống tham lam quá :V Chắc gì đã optimal, tụi geeksforgeeks còn ko ra đáp án đơn giản như vậy mà =]

[rogp10]

Thêm vào tập (ứng với num) 1 số nguyên tố cùng nhau với num là không thỏa đk ngay rồi mà.

[tntxtnt]

nhưng trừ đi thế nào :V ví dụ 2.3.5, 2.3.7, 2.3.11, 2.5.7, 2.5.11, 2.7.11, 3.5.7, 3.5.11, 3.7.11, 5.7.11 (5 số nt chọn 3) đều có số số coprime giống nhau hết thì trừ thế nào =]

[rogp10]

Ví dụ này thì không có cặp nào coprime vì chỉ có 5 thừa số mà đã dùng hết 3 rồi đáp án là 10.