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.

<h1>Sample Input</h1> <h1>Output for Sample Input</h1>
2 6 12 6 13 Case 1: 2 Case 2: -1

题意:给你一个n和m然后这个n每次都可以加一个素因子(不包括n本身),问到达m的最小次数,每次加完后的n是新的n。

思路:因为m只有1000,可以先打出一千以内所有数的素因子集,然后bfs找最小就可以了。

#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());
    }
}

 

相关文章

发表新评论