前言

这道题您看上去难道不是广搜题吗 ？ 数学题的标签是来迷惑人的？（貌似我并不知道数学用在哪里了）

思路

首先为什么考虑广度优先搜索？

不难发现这道题目给出的模数相当的小啊，同时我们要求出最少次数。

于是我们用广搜的话，对于每一个余数我们最多遍历一次，于是时间复杂度为:

O( * ) （Mod 表示余数大小）

同时因为广搜的性质，所以会使得Y第一次被遍历到的时候得到的值就是最优解。

说完了大体思路，就来讲一讲细节的地方吧（这道题目细节挺多的）。

  • 坑点1：给出的 X == Y 的时候，应该直接输出 0

  • 坑点2：给出的 X == 0 并且 Y != X 的时候，肯定怎么样也得不到答案，输出-1

  • 坑点3：Y >= Mod 的时候，假若 X != Y ， 无解

  • 坑点4(最坑的地方): 考虑到给出的 X 可能会大于 Mod，在广搜第一次进队的时候，不要直接把 X 给入队，先要判断 X 和 Mod 的大小关系，倘若 X >= Mod ，那么我们应该入队的是 F(X) 以及 G(X) , 入 X 的话可能会导致段错误。 如果 X < Mod 就没有什么影响，直接入队即可。

  • 坑点5，因为有模意义下的减法，减的时候注意加上模数的平方（因为后面减的数是 Mod 的平方级别的，这道题好像不加也不会死，但是注意一下吧，养成习惯，毕竟NOIP连先乘后除都卡）

  • 坑点6：注意多取模，因为是 x 的三次方，防止挂掉多取模一下

具体的话可以看一看代码吧，有注释。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Mod = 233;
int D[500],Y;

int F(int x)
{
    return (((x % Mod) * (x % Mod) * (x % Mod)) + (x % Mod) * (x % Mod)) % Mod; //模拟F(x)即可
}

int G(int x)
{
    return (((x % Mod) * (x % Mod) * (x % Mod)) + Mod * Mod/*(注意是加上Mod的平方)*/ - (x % Mod) * (x % Mod)) % Mod; 
    //模意义下的减法
}

void BFS(int x)
{
    queue <int> q;
    if(x < Mod)//如果X < Mod 没有影响，入队即可
    {
        q.push(x);
        D[x] = 0;
    }
    else 
    {
        q.push(F(x)),D[F(x)] = 1;//入队的就是F(X) 和 G(X)
        q.push(G(x)),D[G(x)] = 1;
    }
    while(!q.empty())
    {
        int X = q.front();
        q.pop();
        if(X == Y) return ;//已经搜索到了答案
        if(D[F(X)] == 0ll)q.push(F(X)),D[F(X)]= D[X] + 1;//D[F(x)] == 0 就表示还没有被遍历
        if(D[G(X)] == 0ll)q.push(G(X)),D[G(X)] = D[X] + 1;
    }
    return ;
}

signed main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int x;
        cin >> x >> Y;
        if(x == Y){cout << 0 << endl; continue;}//坑点一
        if(Y >= 233 || x == 0){cout << -1 << endl; continue ;}// 坑点2,3
        memset(D,0ll,sizeof(D));
        BFS(x);
        if(D[Y] != 0ll)//如果最后被遍历到，就有解
        cout << D[Y] << endl;
        else cout << -1 << endl;//否则无解
    }
    return 0;
}

总结

总体上来说实现上难度不是很大，但是建议强烈建议读者自己打一打（细节比较多）

是一道搜索 毒瘤 好题