FC - ANTIPRIME

Source: FC89-ANTIPRIME
Tags: Backtracking

Problem:
Hàm d(X) được định nghĩa là số lượng ước của X. Một số nguyên dương K được gọi là phản nguyên tố nếu d(K) > d(X) với mọi X < K. Tìm số phản nguyên tố K lớn nhất mà không lớn hơn N.
N ≤ 1e18.

Ví dụ:
Input:
100
Output:
60

Input:
10
Output:
6

Solution:
Từ điều kiện đã cho, phân tích số phản nguyên tố K thành tích các thừa số nguyên tố của nó, ta có:
- Các thừa số nguyên tố phải liên tiếp nhau.
Nhận xét 2 số K1 = 2 * 3 * 5 và K2 = 2 * 3 * 7, chúng có cùng số lượng ước và số lượng thừa số nguyên tố, nhưng K2 sẽ luôn lớn hơn K1, do đó K2 không thể nào là số phản nguyên tố được.
- Số mũ của các thừa số sẽ giảm dần theo giá trị của chúng.
Nhận xét 2 số K1 = 2^2 * 3^1 * 5^1 và K2 = 2^1 * 3^1 * 5^2, chúng có cùng số lượng ước, số lượng thừa số nguyên tố và các thừa số cũng giống nhau, nhưng K2 sẽ luôn lớn hơn K1, do đó K2 không thể nào là số phản nguyên tố được.
Từ những nhận xét trên, ta có thể thấy số lượng thừa số nguyên tố không quá lớn do trường hợp cần nhiều nhất là 15 thừa số (2 * 3 * 5 * ... * 43 * 47), số mũ tối đa là 59 (2^59), cộng thêm cận như là nếu giá trị đang xét lớn hơn N thì không xét tiếp nữa, có thể thấy số lượng trường hợp cần kiểm tra là rất nhỏ. Lúc này ta chỉ cần tìm giá trị nhỏ nhất có số ước lớn nhất là được.

Code:
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

long long n, res, rescnt;
bool notprime[50];
vector <int> prime;

long long power(int a, int b) {
    long long res = 1;
    for (int i = 1; i <= b; ++i)
        res *= a;
    return res;
}

void backtracking(int i, int max_exponent, long long val, long long cnt) {
    if (val > n) return;
    if (i == prime.size()) {
        if (cnt > rescnt || (cnt == rescnt && val < res))
            res = val, rescnt = cnt;
        return;
    }
    for (int e = max_exponent; e >= 0; --e)
        if (log10(val) + log10(prime[i]) * e <= 18)
            backtracking(i + 1, e, val * power(prime[i], e), cnt * (e + 1));
}

int main() {
    cin >> n;
    for (int i = 2; i < 50; ++i)
        if (!notprime[i]) {
            prime.push_back(i);
            for (int j = 2; i * j < 50; ++j)
                notprime[i * j] = true;
        }
    backtracking(0, 60, 1, 1);
    cout << res;

}