lightoj 1141 - Number Transformation - dblank

# lightoj 1141 - 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.
<h1>Input</h1>
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).
<h1>Output</h1>
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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1000 + 10, Mod = 1000000009;
typedef long long ll;
vector<int> v[N];
int vis[N];
int n, m;
struct node
{
int t;
int x;
};
int bfs()
{
node in, out;
in.t = 0, in.x = n;
queue<node> q;
q.push(in);
vis[n] = 0;
while(!q.empty())
{
in = q.front();
q.pop();
if(in.x == m)
return in.t;
for(int i = 0; i<v[in.x].size(); i++)
{
if(!visin.x + v[in.x] && in.x + vin.x<=m)
{
out.x = in.x + vin.x;
out.t = in.t + 1;
vis[out.x] = 1;
q.push(out);
}
}
}
return -1;
}
int isprime(int x)
{
for(int i = 2; i*i<=x; i++)
{
if(x%i==0)
return 0;
}
return 1;
}
int main()
{
for(int i = 2; i<=1000; i++)
{
for(int j = 2; j<i; j++)
{
if(i%j==0 && isprime(j))
v[i].push_back(j);
}
}
int t;
cin>>t;
for(int cas = 1; cas<=t; cas++)
{
memset(vis, 0, sizeof(vis));
scanf("%d%d", &n, &m);
printf("Case %d: " , cas);
printf("%dn", bfs());
}
}