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

冷不防 2022-05-12 03:14 264阅读 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;
    }