点击打开链接
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 2 6 12 6 13 Sample Output Case 1: 2 Case 2: -1
题意：给出两个数S,T,找出S的质因子，s通过加自己的质因子得到一个数，这个数也加自己的质因子，依次循环，看是否能够等于T.,若能得到，就输出相加次数最少的，若不能输出-1.
AC代码：
#include<stdio.h> #include<math.h> #include<string.h> #include<vector> #include<queue> #include<algorithm> using namespace std; //预先统计出1~1e3每个数的质因子，如果 s == t,自然是一， //如果s 和 t 其中一个是 质数者必定为 -1，其他 BFS int T,t,s,ok,cut; const int MAX=1e3+10; const int INF = 0x3f3f3f3f / 2; int p[MAX],vis[MAX]; vector <int> a[MAX];//用vector来存储每个数的质因子 struct node { int x,nl;//nl表示要加的次数 }; void prime_factor()//查找质因子 { memset(p,0,sizeof(p)); p[1]=1; for(int i=2;i<MAX;i++) { for(int j=i+i;j<MAX;j+=i) p[j]=1;//用打表法把不是素数的数标记，减少了复杂度 } for(int i=2;i<MAX;i++) { for(int j=2;j<i;j++) { if(i%j==0&&!p[j]) a[i].push_back(j); //把每一个数的质因子存起来 } } } void bfs() { memset(vis,0,sizeof(vis)); queue <node> q; vis[s]=1; node o; o.x =s,o.nl=0; q.push(o); while(!q.empty()) { o=q.front() ; q.pop() ; if(o.x==t){ ok=1; cut=min(cut,o.nl );//min()是一个函数包含在algorithm头文件里 continue; } for(int i=0;i<a[o.x].size() ;i++)//a[o.x].size()表示第o.x行存了多少个数 { node w; w.x =o.x +a[o.x ][i],w.nl =o.nl+1; if(w.x <=t&&!vis[w.x]) vis[w.x ]=1,q.push(w); } } } int main() { prime_factor(); scanf("%d",&T); int k=1; while(T--) { scanf("%d%d",&s,&t); if(s==t) printf("Case %d: 0\n",k++); else if(!p[s]) printf("Case %d: -1\n",k++); else { ok=0; cut=INF; bfs(); if(ok) printf("Case %d: %d\n",k++,cut); else printf("Case %d: -1\n",k++); } } return 0; }
