题目链接

Prime Path POJ - 3126

思路

$$ 先筛素数，再bfs，注意前导零。 $$

时间复杂度

$$ O(N)筛素数 $$

代码

#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

class Factor {
public:
    vector<bool> is_prime;
    //pi : min prime factor
    vector<int> prime, pi;

    Factor () {
        sieve((int)1e6 + 10);
    }

    int sieve(int sz) {
        int cnt = 0;

        is_prime.resize(sz + 1, false);
        pi.resize(sz + 1, 0);
        for (int i = 1; i <= sz; i++) {
            pi[i] = i;
        }
        for (int i = 2; i <= sz; i++) {
            if (pi[i] == i) {
                prime.push_back(i);
                is_prime[i] = true;
                ++cnt;
            }
            for (int j = 0; j < cnt && 1LL * prime[j] * i <= sz; j++) {
                pi[prime[j] * i] = prime[j];
                if (i % prime[j] == 0) {
                    break;
                }
            }
        }
        return cnt;
    }

    inline long long mul_mod(long long a, long long b, long long mod) const {
        if (mod <= 1000000000) {
            return a * b % mod;
        } else if (mod <= 1000000000000LL) {
            return (((a * (b >> 20) % mod) << 20) + (a * (b & ((1 << 20) - 1)))) % mod;
        } else {
            long long d = (long long) floor(a * (long double)b / mod + 0.5);
            long long res = (a * b - d * mod) % mod;
            if (res < 0) {
                res += mod;
            }
            return res;
        }
    }

    long long pow_mod(long long a, long long b, long long mod) {
        long long res = 1;
        while (b) {
            if (b & 1) {
                res = mul_mod(res, a, mod);
            }
            a = mul_mod(a, a, mod);
            b >>= 1;
        }
        return res;
    }

    bool witness(long long a, long long n) {
        int t = 0;
        long long u = n - 1;
        while ((~u) & 1) {
            t++;
            u >>= 1;
        }
        long long x = pow_mod(a, u, n);
        long long xx = 0;
        while (t--) {
            xx = mul_mod(x, x, n);
            if (xx == 1 && x != 1 && x != n - 1) {
                return true;
            }
            x = xx;
        }
        return xx != 1;
    }

    inline long long randll() {
        return (long long)rand() << 30 | rand();
    }



    bool miller(long long n) {
        if (n < 2) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        if (n < (int)is_prime.size()) {
            return is_prime[n];
        }
        if ((~n) & 1) {
            return false;
        }
        for (int i = 0; i <= 7; i++) {
            if (witness(randll() % (n - 1) + 1, n)) {
                return false;
            }
        }
        return true;
    }

    // fast gcd
    long long gcd(long long a, long long b) {
        long long res = 1;
        while (a != 0) {
            if (((~a) & 1) && ((~b) & 1)) {
                res <<= 1;
                a >>= 1;
                b >>= 1;
            } else if ((~a) & 1) {
                a >>= 1;
            } else if ((~b) & 1) {
                b >>= 1;
            } else {
                if (a < b) {
                    swap(a, b);
                }
                a -= b;
            }
        }
        return res * b;
    }

    long long rho(long long n) {
        static long long a[1001000];
        while (true) {

            long long X = rand() % n, Z, T = 1;

            long long *lY = a, *lX = lY;
            int tmp = 20;

            int C = rand() % 10 + 3;
            X = mul_mod(X, X, n) + C;
            *(lY++) = X;
            lX++;

            long long Y = mul_mod(X, X, n) + C;
            *(lY++) = Y;

            while (X != Y) {
                long long t = X - Y + n;
                Z = mul_mod(T, t, n);
                if (Z == 0) {
                    return gcd(T, n);
                }
                tmp--;
                if (tmp == 0) {
                    tmp = 20;
                    Z = gcd(Z, n);
                    if (Z != 1 && Z != n) {
                        return Z;
                    }
                }
                T = Z;
                Y = *(lY++) = mul_mod(Y, Y, n) + C;
                Y = *(lY++) = mul_mod(Y, Y, n) + C;
                X = *(lX++);
            }
        }
    }

    vector<long long> fac;
    void print_fac() {
        for (int i = 0; i < (int)fac.size(); i++) {
            printf("%lld ", fac[i]);
        }
        puts("");
    }

    void _factor(long long n) {
        int sz = (int)fac.size();
        for (int i = 0; i < sz; i++) {
            if (n % fac[i] == 0) {
                n /= fac[i];
                fac.push_back(fac[i]);
            }
        }
        if (n <= (int)pi.size()) {
            while (n != 1) {
                fac.push_back(pi[n]);
                n /= pi[n];
            }
            return;
        }
        if (miller(n)) {
            fac.push_back(n);
            return;
        } else {
            long long x = rho(n);
            _factor(x);
            _factor(n / x);
        }

    }

    // gen all prime factors
    vector<long long> fact_big(long long n) {
        fac.clear();
        _factor(n);
        return fac;
    }
};
Factor fa;
const int MAXN = 1e4 + 10;
int vis[MAXN];

string itos(int x) {
    string res;
    for (int i = 0; i < 4; i++) {
        res +='0' + x % 10;
        x /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

int stoi(string &s) {
    int res = 0;
    for (int i = 0; i < 4; i++) {
        res *= 10;
        res += s[i] - '0';
    }
    return res;
}

int bfs(int a, int b) {
    memset(vis, -1, sizeof vis);
    queue<int> que;
    que.push(a);
    vis[a] = 0;
    while (!que.empty()) {
        int cur = que.front();
        if (cur == b) {
            return vis[b];
        }
        que.pop();
        string s = itos(cur);
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j <= 9; j++) {
                string ss = s;
                ss[i] = '0' + j;
                int now = stoi(ss);
                if (now < 1000) {
                    continue;
                }
                if (fa.is_prime[now] && vis[now] == -1) {
                    vis[now] = vis[cur] + 1;
                    que.push(now);
                }
            }
        }
    }
    return -1;
}


int main() {
    int T;
    scanf("%d", &T);// don't forget &
    while (T--) {
        int a, b;
        scanf("%d%d", &a, &b);// don't forget &
        int ans = bfs(a, b);
        if (ans == -1) {
            puts("Impossible");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}