题目链接：点击打开链接

1141 - Number Transformation    PDF (English)StatisticsForum Time Limit: 2 second(s)Memory Limit: 32 MB

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

Output for Sample Input

2

6 12

6 13

Case 1: 2

Case 2: -1

 

大意：题意：给两个数 s ，t ，用 s 加上它的素因子（不包括 1 和它自身）得到另外一个数，然后重复之前的操作，每次加上当前数的素因子。。。直到得到 t 为止，问最少经过多少次的得到 t ，若得不到输出 -1

#include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; int a,b; bool shu[1010]={1,1}; bool vis[1010]; struct node { int val,step; }; int bfs() { memset(vis,0,sizeof(vis)); queue<node> Q; node now,next; now.val=a,now.step=0; Q.push(now); while(!Q.empty()) { now=Q.front(); Q.pop(); if(now.val==b) return now.step; for(int i=2;i<now.val;i++) { if(now.val%i||shu[i]) continue; if(now.val+i>b||vis[now.val+i]) continue; vis[now.val+i]=1; next.val=now.val+i; next.step=now.step+1; Q.push(next); } } return -1; } int main() { for(int i=2;i<=1000;i++) { if(shu[i]) continue; for(int j=i*2;j<=1000;j+=i) shu[j]=1; } int t,text=0; scanf("%d",&t); while(t--) { scanf("%d%d",&a,&b); printf("Case %d: %d\n",++text,bfs()); } return 0; }