C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 3016 Prime Path

Problem

阿P给阿K出了一个难题,他给阿K两个素数A,B,保证A,B的位数相同且为4位或5位。

阿K只能对A作一种操作,即将其中一位数字改成另一个数字,要求每次操作后得到的数还是一个素数,问最少多少次可以从A变到B

Solution

按每一位bfs

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<stdio.h>
#include<set>
#include<iostream>
#include<stack>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int mod=998244353;
ll mo(ll a,ll p){
return a>=p?a%p:a;
}
inline int rd() {
int x = 0, f = 1;
char ch;
while (ch < '0' || ch > '9') {
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
inline ll gcd(ll x, ll y){
return y==0?x:gcd(y,x%y);
}
inline ll speed(ll a,ll b){
ll cur=a,anss=1;
while(b){
if(b&1) anss=anss*cur;
cur=cur*cur;
b>>=1;
}
return anss;
}
const int MAXN=1e5;
bool ipr[MAXN+20];
int cnt,pri[MAXN/5];
void prime(){//埃式筛法
int N=sqrt(MAXN)+0.5,mul;
memset(ipr,true,sizeof(ipr));
ipr[1]=false;
for(int i=2;i<=N;i++){
if(ipr[i]==true){
i==2?mul=1:mul=2;
for(int j=i*i;j<=MAXN;j+=i*mul){
ipr[j]=false;
}
}
}
for(int i=2;i<=MAXN;i++){
if(ipr[i]==true){
pri[++cnt]=i;
}
}
}
int T,a,b;
int wei(int x){
int ret=0;
do{
x/=10;
ret++;
}while(x);
return ret;
}
struct E{
int num,cnt;
};
bool f[100020];
int bits[10];
int comb(int t){
int ret=0;
for(int i=t;i>=1;i--){
ret*=10;
ret+=bits[i];
}
return ret;
}
int bfs(){
int t=wei(a);
queue<E>q;
q.push((E){a,0});
f[a]=true;
while(!q.empty()){
E cur=q.front();q.pop();
if(cur.num==b) return cur.cnt;
for(int i=1;i<=t;i++){
bits[i]=cur.num%10;
cur.num/=10;
}
//cout<<comb(t)<<endl;
for(int i=1;i<=t;i++){
int d=bits[i];
for(int j=0;j<=9;j++){
if(j==d||(i==t&&j==0)) continue;
bits[i]=j;
int nex=comb(t);
//cout<<nex<<endl;
if(ipr[nex]&&!f[nex]){
f[nex]=true;
q.push((E){nex,cur.cnt+1});
//cout<<nex<<endl;
}
}
bits[i]=d;
}
}
return -1;
}
int main(){
io_opt;
prime();
cin>>T;
while(T--){
memset(f,false,sizeof(f));
cin>>a>>b;
if(a==b){
cout<<0<<endl;
continue;
}
int ans=bfs();
if(ans==-1){
cout<<"No solution"<<endl;
}
else{
cout<<ans<<endl;
}
}
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/4657/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!