使用最少数量的给定操作将数字 m 转换为 n

Question

问题：

给定 2 个整数 N 和 M。使用给定操作的最少次数将数字 N 转换为 M。

操作是：

N 平方 (N = N^2)
如果 N 可被 P 整除（N = N / P 且 N % P == 0），则将 N 除以素数 P

参赛者：

N, M <= 10^9

示例：

N = 12, M = 18

最少的操作是：

N /= 2 -> N = 6
N = N^2 -> N = 36
N /= 2 -> N = 18

我的看法：

我正在尝试使用 BFS 来解决这个问题。对于每个数字，其他数字的可用边缘是操作。但是它超过了时间限制。有没有更好的办法解决这个问题？

这是我的 BFS 代码：

queue<pair<int,int> > q;
vector<long long> pr;
ll m,n;
bool prime[MAXN+1];

void solve()
{
    while (!q.empty())
    {
        pii x=q.front();
        q.pop();
        if (x.first==m)
        {
            cout << x.second;
            return;
        }
        if (x.first==1) continue;
        for(ll k:pr)
        {
            if (k>x.first) break;
            if (x.first%k==0) q.push({x.first/k,x.second+1});
        }
        q.push({x.first*x.first,x.second+1});
    }
}

Answer 1

该算法使用质因数中 N 和 M 的分解，跟踪相应的指数。

如果M有一个质因数N没有，则无解（代码returns -1）。

如果N有一些M没有的质因数，那么第一步就是用N除以这些质数。
对应的运算次数为对应的指数之和

在这个阶段，我们得到两个数组A和B对应公共素数的指数，分别为N和M。
值得注意的是，在这个阶段，所涉及的素数的值不再相关，只有指数才重要。

然后必须确定最少的平方数（= 乘以 2 的指数）。
是最小的 k 使得 A[i] >= 2^k B[i] 对于所有索引 i.
乘法次数只加一次运算次数，因为所有指数同时乘以2。

最后一步是确定，对于每一对 (a, b) = (A[i], B[i])，从 a 到 b 所需的减法次数，同时精确地执行 k 乘法2. 这是按照以下规则执行的：

- if (k == 0) f(a, b, k) = a-b
- Else:
    - if ((a-1)*2^k >= b: f(a, b, k) = 1 + f(a-1, b, k)
    - else: f(a, b, k) = f(2*a, b, k-1)

复杂度主要由质数因子的分解决定：O(sqrt(n))

代码：

这段代码比较长，但是如果调试和分析需要辅助例程的话，大部分都包含了。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

void print (const std::vector<int> &v, const std::string s = "") {
    std::cout << s;
    for (auto &x: v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

void print_decomp (int n, const std::vector<int> &primes, const std::vector<int> &mult) {
    std::cout << n << " = ";
    int k = primes.size();    
    for (int i = 0; i < k; ++i) {
        std::cout << primes[i];
        if (mult[i] > 1) std::cout << "^" << mult[i];
        std::cout << " ";
    }
    std::cout << "\n";
}

void prime_decomp (int nn, std::vector<int> &primes, std::vector<int> &mult) {
    int n = nn;
    if (n <= 1) return;

    if (n % 2 == 0) {
        primes.push_back(2);
        int cpt = 1;
        n/= 2;
        while (n%2 == 0) {n /= 2; cpt++;}
        mult.push_back (cpt);
    }
    int max_prime = sqrt(n);
    int p = 3;
    while (p <= max_prime) {
        if (n % p == 0) {
            primes.push_back(p);
            int cpt = 1;
            n/= p;
            while (n%p == 0) {n /= p; cpt++;}
            mult.push_back (cpt);
            max_prime = sqrt(n);
        }
        p += 2;
    }
    if (n != 1) {
        primes.push_back(n);
        mult.push_back (1);
    }
    print_decomp (nn, primes, mult);
}

//  Determine the number of subtractions to go from a to b, with exactly k multiplications by 2

int n_sub (int a, int b, int k, int power2) {
    if (k == 0){
        if (b > a) exit(1);
        return a - b;
    }
    //if (a == 1) return n_sub (2*a, b, k-1, power2/2);
    if ((a-1)*power2 >= b) {
        return 1 + n_sub(a-1, b, k, power2);
    } else {
        return n_sub (2*a, b, k-1, power2/2);
    }
    return 0;
}

//  A return of -1 means no possibility

int n_operations (int N, int M) {
    int count = 0;
    if (N == M) return 0;
    if (N == 1) return -1;
    std::vector<int> primes_N, primes_M, expon_N, expon_M;
//  Prime decomposition
    prime_decomp(N, primes_N, expon_N);
    prime_decomp (M, primes_M, expon_M);
//  Compare decomposition, check if a solution can exist, set up two exponent arrays
    std::vector<int> A, B;
    int index_A = 0, index_B = 0;
    int nA = primes_N.size();
    int nB = primes_M.size();
    while (true) {
        if ((index_A == nA) && (index_B == nB)) {
            break;
        }
        if ((index_A < nA) && (index_B < nB)) {
            if (primes_N[index_A] == primes_M[index_B]) {
                A.push_back(expon_N[index_A]);
                B.push_back(expon_M[index_B]);
                index_A++; index_B++;
                continue;
            }
            if (primes_N[index_A] < primes_M[index_B]) {
                count += expon_N[index_A];
                index_A++;
                continue;
            }
            return -1;  // M has a prime that N doesn't have: impossibility to go to M
        }
        if (index_B != nB) {        // impossibility
            return -1;
        }
        for (int i = index_A; i < nA; ++i) {
            count += expon_N[i];    // suppression of primes in N not in M
        }
        break;
    }
    std::cout << "1st step, count = " << count << "\n";
    print (A, "exponents of N: ");
    print (B, "exponents of M: ");
    
//  Determination of the number of multiplications by two of the exponents (= number of squares)
    int n = A.size();
    int n_mult2 = 0;
    int power2 = 1;
    for (int i = 0; i < n; ++i) {
        while (power2*A[i] < B[i]) {
            power2 *= 2;
            n_mult2++;
        }
    }
    count += n_mult2;
    std::cout << "number of squares = " << n_mult2 << "  -> " << power2 << "\n";
    
//  For each pair of exponent, determine the number of subtractions, 
//  with a fixed number of multiplication by 2

    for (int i = 0; i < n; ++i) {
        count += n_sub (A[i], B[i], n_mult2, power2);
    }
    
    return count;
}


int main() {
    int N, M;
    std::cin >> N >> M;
    auto ans = n_operations (N, M);
    std::cout << ans << "\n";
    
    return 0;
}

使用最少数量的给定操作将数字 m 转换为 n

Convert a number m to n using minimum number of given operations

algorithm

breadth-first-search