LightOJ - 1141 Number Transformation ——————BFS+素因子分解-蒲公英云

LightOJ - 1141 Number Transformation ——————BFS+素因子分解

冷不防 2022-05-12 03:14 262阅读 0赞

**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.

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

要注意A是不断变化的，所以它的质因子也会变化
还有啊注意A的质因子不能有1，A

#include<bits/stdc++.h>
using namespace std;
int s,t,ans;
int cnt;
int num,T;
int p[1000];
bool vis[3000];
struct node {
    int x,step;
    node(){
    };
    node(int _x,int _step)
    {
        x=_x; step=_step;
    }
    bool operator < (const node &b)const
    {
        return step>b.step;
    }
};
void init(int n)
{
    memset(p,0,sizeof(p));
    cnt=0;
    int z=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            p[cnt++]=i;
            while(n%i==0)  n/=i;
        }
    }
    if(n!=1&&n!=z)    p[cnt++]=n;
}
void bfs(int s,int t)
{
    memset(vis,0,sizeof(vis));
    priority_queue<node> que;
    node e1,e2;
    que.push(node(s,0));
    vis[s]=1;
    while(que.size())
    {
        e1=que.top();que.pop();
        if(e1.x==t)
        {
            ans=e1.step;
            break;
        }
        init(e1.x);
        for(int i=0;i<cnt;i++)
        {
            e2.x = e1.x + p[i];
            e2.step = e1.step + 1;
            if(!vis[e2.x] && e2.x <= t)
            {
                vis[e2.x]=1;
                if(e2.x==t)
                {
                    ans=e2.step;
                    break;
                }
                que.push(e2);
            }
        }
    }
}
int main()
{
    scanf("%d",&num);
    T=num;
    while(num--)
    {
        scanf("%d %d",&s,&t);
        ans=-1;
        bfs(s,t);
        printf("Case %d: %d\n",T-num,ans);
    }
    return 0;
}