题解

单元测评时忘了用埃式筛了，后悔莫及（

#include <iostream>
#include <cstdio>
#include <queue>
#include <memory.h>
using namespace std;
bool isprime[10005];
bool vis[10005];
struct node{
	int val, step;
};
int n;
void _init(){//埃式筛模版O(nloglogn)
    const int n = 10005;
    vis[0] = vis[1] = 1;
    for(int i = 2; i * i <= n; i++){
        if(!isprime[i]){
            for(int j = i << 1; j <= n; j += i) isprime[j] = 1;
        }
    }
}
int f(int x, int i, int j){
	return x / i * i + j * i / 10 + x % (i / 10);
}
int dfs(int x){//我用的就是深搜！！！时间复杂度：O(10000)
	queue <node> q;
	q.push({x, 0});
	vis[x] = 1;
	while(!q.empty()){
		node head = q.front();
		q.pop();
		//cout << head.val << ' ' << n << ' ' << head.step << endl;
		if(head.val == n) return head.step;
		for(int i = 10; i <= 10000; i *= 10){
			for(int j = 0; j <= 9; j++){
				int v = f(head.val, i, j);
				//cout << v << ' ' << head.step + 1 << endl;
				if(!vis[v] && !isprime[v] && v >= 1000){
					vis[v] = 1;
					q.push({v, head.step + 1}); 
				}
			}
		}
	}return 0;
}
int main(){
    _init();
	int t, m;
	scanf("%d", &t);
	while(t--){
		memset(vis, 0, sizeof(vis));
		scanf("%d%d", &m, &n);
		printf("%d\n", dfs(m));
	}
	
	return 0;
}

单个数据时间复杂度：$O(10000)$
整体时间复杂度：$O(18000+10000t)$