Bài F - Technocup 2019 - Elimination Round 2

Bài F:
Đề bài:
Bạn được cho hai số nguyên a và b. Có hai thao tác sau có khả năng xảy ra:
1. Nhân một số với số nguyên tố p bất kỳ.
2. Chia một số cho ước nguyên tố p của nó.
Số thao tác tối thiểu bạn cần dùng để đạt được hai số nguyên mà có số ước giống nhau là bao nhiêu ? Bạn được cho một vài cặp, bạn cần tìm ra câu trả lời cho chúng.
Đầu vào:
+ Dòng đầu tiên chứa số nguyên t (1<=t<=10^5) - số cặp các số nguyên mà bạn cần tính.
+ t dòng tiếp theo, mỗi dòng chứa hai số nguyên a(i) và b(i) (1<=a(i),b(i)<=10^6).
Đầu ra:
+ In ra t dòng- là đáp án của bài toán.
Ví dụ:
Đầu vào:
8
9 10
100 17
220 70
17 19
4 18
32 20
100 32
224 385
Đầu ra:
1
3
1
0
1
0
1
1
1
Chú thích:
+ Các số dưới đây có cùng số ước, dưới đây là cách tối ưu đạt được trong mỗi test:
+ (27,10) - có 4 ước số.
+ (100,1156) - có 9 ước số.
+ (220,140) - có 12 ước số.
+ (17,19) - có 2 ước số.
+ (12,18) - có 6 ước số.
+ (50.32) - có 6 ước số.
+ (224,1925) - có 12 ước số
Hướng dẫn:
Chú ý rằng nếu $a=\prod\limits_{i=1}^{k}p_{i}^{x_i}$ thì $d(a)=\prod\limits_{i=1}^{k}(x_i+1)$. Điều này suy ra rằng chúng ta có thể thiết lập một ánh xạ a đến vector (x(1),x(2),...,x(k)), ở đó x(1)>=x(2)>=...>=x(k), bởi vì thứ tự các mũ của chúng không phải là vấn đề.
Và các 2 thao tác trên có ý nghĩa rằng: Hoặc chúng ta sẽ cộng thêm 1 vào số mũ của một số nào đó, hoặc thêm số 1 vào tận cùng của vector hoặc trừ đi 1 từ một số mũ nào đó và sắp xếp lại vector sau đó. Chỉ có 289 vector khác nhau như vậy cho các số lên tới 10^6, vì vậy chúng ta chỉ cần tính toán 41616 khoảng cách.
  Ý nghĩ đầu tiên có thể là chạy thuật toán Floyd-warshall trên 289 đỉnh này, sẽ phù hợp thời gian. Sau đó với mỗi cặp (x,d) chúng ta có thể tìm số thao tác ít nhất cần làm để tạo ra với vector x để mà sinh ra số mà có d ước. Để tìm câu trả lời cho (x,y), chúng ta chỉ đơn giản có thể lặp lại trên tất cả các giá trị có thể của d. Nhưng có một số trường hợp khó khăn. Ví dụ, với các số 2^19 và 2^2.3^6, câu trả lời là 1, bởi vì sau khi nhân 2 vào số đầu tiên tất cả 2 số đều có cùng 21 ước. Nhưng số 2^20>10^6, và vector(20) không thuộc 289 đỉnh. Vì vậy, chúng ta cần phải xem xét một số vector khác.
 Dù sao, hãy chạy thuật toán này để xem khoảng cách tối đa giữa hai số lên tới 10^6 có thể là bao nhiêu ? Hóa ra tron 10 thao tác, bất kỳ hai số nào cũng có thể được dẫn đến có cùng số ước trong đường dẫn không vượt quá 10^6.
 Điều này có nghĩa là mỗi số có thể trong đường dẫn tối ưu thỏa mãn $\sum\limits_{i=1}^{k}x_i<30$, bởi vì đối với các số đầu vào tổng này không vượt quá 16 và không thể có quá 10 thao tác với mỗi số. Điều kiện này cung cấp cho chúng ta tất cả các vecto quyền hạn cần thiết để coi là điểm giữa cho các cặp có thể có trong đầu vào. Có 28629 vector như vậy. Bây giờ chúng tôi chạy 289 bfs trên biểu đồ được tạo với khởi đầu mỗi vector có thể từ đầu và xây dựng cấu trúc dữ liệu giống nhau cho các cặp (x,d) như đã giải thích trước đó, cho phép chúng tôi tìm câu trả lời cho tất cả các vector số lên tới 10^6.
 Giải pháp này hoạt động trong 2,5s trên các máy chủ cf, vẫn còn quá chậm. Nhưng điều quan trọng là chúng ta đã tìm thấy câu trả lời cho tất cả các cặp vector đầu vào. Vì vậy, chúng ta có thể cố gắng loại bỏ một số đỉnh không cần thiết và chỉ cần kiểm tra xem tổng số câu trả lời không thay đổi. Một trong cách tăng tốc có thể chỉ xem xét các vector tạo ra số lượng ước không quá một số hợp lý. Số lượng ước tính tối đa của một số vector cần thiết là 288, vì vậy các hằng số ma thuật như 300 trở lên sẽ hoạt động. Một cách tăng tốc có thể khác là giảm biên giới trên tổng sức mạnh từ 30 xuống 22, điều này là chính xác.
Lời giải:

#include <bits/stdc++.h>
#pragma GCC optimize 03
using namespace std;
const int N = 1e6 + 1;


set <vector<int> > s;
vector <int> v[N];
int top[N];
vector <vector<int> > qt;
set <int> H;
int dp[289][31][1201];

int get(int a) {
    for (int i = 0; i < 289; ++i)
    if (qt[i] == v[a])
        return i;
}

int main() {
    int i, j, k, n, l;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    for (i = 1; i < N; ++i) {
        v[i].resize(7);
        for (j = 0; j < 7; ++j)
            v[i][j] = 1;
    }
    for (i = 2; i < N; ++i)
    if (top[i] == 0) {
        for (j = 1; i * j < N; ++j) {
            int x = j;
            int p = 2;
            while (x % i == 0) {
                x /= i;
                ++p;
            }
            v[i * j][top[i * j]] = p;
            ++top[i * j];
        }
    }
    l = 0;
    for (i = 1; i < N; ++i) {
        sort(v[i].begin(), v[i].end());
        l = max(l, (int)v[i].size());
        if (v[i].size() > 0) {
            s.insert(v[i]);
        }
    }
    for (set <vector <int> > :: iterator it = s.begin(); it != s.end(); ++it)
        qt.push_back((*it));
    for (i = 0; i < qt.size(); ++i)
    for (j = 0; j <= 30; ++j)
    for (l = 0; l <= 1200; ++l)
        dp[i][j][l] = 999;
    for (int y = 0; y < qt.size(); ++y) {
        vector <int> T;
        for (j = 0; j < 7; ++j)
            T.push_back(qt[y][j]);
        for (j = 0; T.size() < 30; ++j)
            T.push_back(1);
        dp[y][0][1] = 0;
        for (i = 0; i < 30; ++i)
        for (j = 1; j <= 1200; ++j)
        if (dp[y][i][j] < 999)
        for (l = max(1, T[i] - 30); j * l <= 1200 && l <= min(1200, T[i] + 30); ++l)
            dp[y][i + 1][j * l] = min(dp[y][i + 1][j * l], dp[y][i][j] + abs(T[i] - l));
    }
    cin >> n;
    for (i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        int p1 = get(a), g1 = get(b);
        int ans = 9000;
        for (j = 1; j <= 1200; ++j)
            ans = min(ans, dp[p1][30][j] + dp[g1][30][j]);
        cout << ans << "\n";

    }
}