Editorial for Educational Backtracking: Số ước số


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: marvinthang

Backtrack kết hợp với tham lam, theo công thức tính số ước nguyên dương của một số thì ta chỉ quan tâm tới bậc của các thừa số nguyên tố chứ không quan tâm đến giá trị của các thừa số nguyên tố đó. Vì để số đó nhỏ nhất có thể (đảm bảo nhỏ hơn hoặc bằng ~n~) thì ta ưu tiên chọn các thừa số nguyên tố nhỏ nhất, tầm ~20~ số đầu (vì tích ~20~ số nguyên tố đầu tiên đủ lớn hơn ~10^{18}~), và xét bậc của các thừa số nguyên tố đó giảm dần.

Độ phức tạp tối đa: số nghiệm nguyên không âm của bất phương trình: ~a_1 + a_2 + \dots + a_{20} \leq 60~ ~(a_1 \geq a_2 \geq ... \geq a_{20})~ ( xấp xỉ ~5 * 10^6~ nghiệm) nhưng thực tế chạy nhanh hơn rất nhiều.

Code mẫu:

#include <bits/stdc++.h>

using namespace std;

vector <int> primes;
long long N, res;

void init(void) {
    for (int i = 2; (int) primes.size() < 20; ++i) {
        bool check = true;
        for (int j = 2; j * j <= i; ++j) if (i % j == 0) check = false;
        if (check) primes.push_back(i);
    }
}

void backtracking(int i, int maxExp, long long val, long long numDiv) {
    res = max(res, numDiv);
    if (i == (int) primes.size()) return;
    for (int d = 1; d <= maxExp; ++d) {
        if (N / primes[i] < val) return;
        val *= primes[i];
        backtracking(i + 1, d, val, numDiv * (d + 1));
    }
}

long long process(void) {
    cin >> N;
    res = -1;
    backtracking(0, 64, 1, 1);
    return res;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    init();
    int t; cin >> t;
    while (t--) cout << process() << '\n';
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.