LightOJ 1141 Number Transformation-白红宇

LightOJ 1141 Number Transformation

阅读量：4311 次

发布时间：2019-06-06

本文共 1587 字，大约阅读时间需要 5 分钟。

Number Transformation

In this problem, you are given an integer number s. You can transform any integer number A to another integer number B by adding x to A. This x is an integer number which is a prime factor of A (please note that 1 and A are not being considered as a factor of A). Now, your task is to find the minimum number of transformations required to transform s to another integer number t.

Input

Input starts with an integer T (≤ 500), denoting the number of test cases.Each case contains two integers: s (1 ≤ s ≤ 100) and t (1 ≤ t ≤ 1000).

Output

For each case, print the case number and the minimum number of transformations needed. If it's impossible, then print -1.

Sample Input

26 126 13

Sample Output

Case 1: 2Case 2: -1

题意每次s加上质因数，然后再求加过后结果的质因数，再加上去，到最后是否可以等于t；

题解 bfs ，一开始老是想dfs，并且题意还理解的有偏差。以下是代码。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAX=1000000;int pri[MAX],dis[MAX];int kk=0;void pirme()//打表求素数 { memset(pri,0,sizeof(pri)); pri[0]=pri[1]=1; for(int i=2;i

qu; qu.push(a) ; dis[a]=0;//起始位置为0； while(!qu.empty() ) { int x=qu.front() ; qu.pop() ; if(x==b) return ; for(int i=2;i

b) break; if(dis[x+i]>dis[x]+1)//更改步数 { dis[x+i]=dis[x]+1; qu.push(x+i); } } } } }int main(){ int T; scanf("%d",&T); pirme(); int Case=1; while(T--) { int s,t; scanf("%d%d",&s,&t); bfs(s,t); if(dis[t]!=0x3f3f3f3f) printf("Case %d: %d\n",Case++,dis[t]); else printf("Case %d: -1\n",Case++); } return 0;}

代码水平还是差啊，

转载于:https://www.cnblogs.com/-xiangyang/p/9220266.html

你可能感兴趣的文章