[牛客] 函数的魔法(bfs)

先用bfs求从a走到b的步数，用二维数组dis保存

(dis[a][b]表示从a到b操作的最少次数)

对于a==b或者b>233的情况直接输出答案

因为a是可能大于等于233的，所以每次不是直接输出dis[a][b]， 而是求出f=F(a)和g=G(a)的值，讨论情况

dis[f][b]和dis[g][b]都不存在，输出-1

dis[f][b]和dis[g][b]有一个存在，输出的答案要加1，因为a转化为f、g也算一次操作

dis[f][b]和dis[g][b]都存在时，要输出较小的再加1

#include <bits/stdc++.h>
using namespace std;
#define mset(var,val) memset(var,val,sizeof(var))
#define lowbit(x) (x&-x)
#define ls i<<1
#define rs i<<1|1
typedef long long int lli;
typedef unsigned long long ull;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const long double eps=1e-20;
const int mod=1e+9;
const int M=250;
int dis[M][M],k[2]={-1,1},m=233;
queue<int> q;
void bfs(int x)
{
    dis[x][x]=0;
    q.push(x);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=0;i<2;i++)
        {
            int next=(now*now*now+now*now*k[i])%m;
            if(dis[x][next]!=-1)continue;
            dis[x][next]=dis[x][now]+1;
            q.push(next);
        }
    }
}
int main()
{
    mset(dis,-1);
    for(int i=0;i<m;i++)
        bfs(i);
    int t,a,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&b);
        if(a==b){printf("0\n");continue;}
        if(b>=m){printf("-1\n");continue;}
        a%=m;
        int f=(a*a*a+a*a)%m;
        int g=(a*a*a-a*a)%m;
        if(dis[f][b]==-1&&dis[g][b]==-1) printf("-1\n");
        else if(dis[f][b]==-1) printf("%d\n",dis[g][b]+1);
        else if(dis[g][b]==-1) printf("%d\n",dis[f][b]+1);
        else printf("%d\n",min(dis[f][b]+1,dis[g][b]+1));
    }
}