UVa 11730
題目
http://domen111.github.io/UVa-Easy-Viewer/?11730
給兩個數字 $S, T$
數字 $A$ 可以透過加上 $A$ 除了本身以外的質因數轉移成 $A’$
問最少透過多少次轉移從 $S$ 變成 $T$,若無解則輸出 $-1$
想法
因為要找的是最少的步數,所以可以想到用 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
| #include<iostream> using namespace std; int s, t, px, cur, Case=1, prime[1005], que[1000000], dis[1005]; bool not_prime[1005], vis[1005];
void build(){ for(int i=0 ; i<=1000 ; i++){ not_prime[i] = false; } int i; px=1; prime[0] = 2; for(i=3 ; i*i<=1000 ; i+=2){ if(!not_prime[i]){ prime[px++] = i; for(int j=i*i ; j<=1000 ; j+=2*i){ not_prime[j] = true; } } } for( ; i<=1000 ; i+=2){ if(!not_prime[i]){ prime[px++] = i; } } }
int BFS(int start, int end){ que[0] = start; vis[start] = true; for(int i=0, j=1 ; i<j ; i++){ cur = que[i]; if(cur == end){ return dis[end]; } for(int k=0 ; k<px && prime[k]<cur && cur+prime[k]<=end ; k++){ if(cur%prime[k] == 0 && !vis[cur + prime[k]]){ que[j++] = cur + prime[k]; vis[cur + prime[k]] = true; dis[cur + prime[k]] = dis[cur] + 1; } } } return -1; }
int main(){ build(); while(cin>>s>>t && (s!=0 && t!=0)){ for(int i=0 ; i<=1000 ; i++) dis[i] = 0, vis[i] = false; cout<<"Case "<<Case++<<": "<<BFS(s, t)<<"\n"; } return 0; }
|