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 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).
For each case, print the case number and the minimum number of transformations needed. If it's impossible, then print -1.
2
6 12
6 13
Case 1: 2
Case 2: -1
题意：A+s=B,s为A的质因子，最少需要重复多少次可以得到B 注意A''=A+s s为新得到的A''的质因子，刚开始理解错了。。。
code：
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define inf 0x3f3f3f3f using namespace std ; int a [ 1000 ] = { 1, 1 } ; int num [ 1000 ] ; void su ( ) { memset (a, 0, sizeof (a ) ) ; for ( int i = 2 ;i < 1010 ;i ++ ) { if (a [i ] ) continue ; for ( int j = 2 *i ;j <= 1000 ;j + =i ) a [j ] = 1 ; } } void f ( int s, int t ) { queue < int >q ; memset (num, 0x3f, sizeof (num ) ) ; //初始化为无穷大 num [s ] = 0 ; q. push (s ) ; while ( !q. empty ( ) ) { int v =q. front ( ) ; q. pop ( ) ; if (v ==t ) return ; for ( int i = 2 ;i <v ;i ++ ) { if (v %i == 0 &&a [i ] == 0 ) { if (v +i >t ) break ; if (num [i +v ] >num [v ] + 1 ) num [v +i ] =num [v ] + 1, q. push (v +i ) ; } } } } int main ( ) { int T,s,t ; su ( ) ; scanf ( "%d", &T ) ; int k = 1 ; while (T -- ) { scanf ( "%d%d", &s, &t ) ; f (s,t ) ; if (num [t ] ! =inf ) printf ( "Case %d: %d\n",k ++,num [t ] ) ; else printf ( "Case %d: %d\n",k ++, - 1 ) ; } return 0 ; }