牛客练习赛35 C 函数的魔法 bfs

牛客练习赛35 C 函数的魔法 bfs

 题目：

链接：
来源：牛客网
 

题目描述

一位客人来到了此花亭，给了女服务员柚一个数学问题：我们有两个函数，F(X)函数可以让X变成（X*X*X+X*X）mod 233。G(X)函数可以让X变成（X*X*X-X*X）mod 233，我们可以任意的对A使用F(X),和G(X)，问最少需要多少次使用这两个函数让A变成B。

输入描述:

第一行输入一个T，表示T组案例（T<100000），然后输入两个整数A,B，表示我们需要把A变成B。（0<=A<=2000000000，0<=B<=2000000000）

输出描述:

输出一个整数表示从A到B最少需要多少次操作，如果不能请输出-1.

示例1

输入

复制

1
2 186

输出

复制

2

说明

我们首先使用F(X)，将2变成(2*2*2+2*2)mod 233=12。然后我们再将12通过G(X)，变成(12*12*12-12*12)mod 233=186

 思路：

将求出的结果的余数作为bfs的对象，进行bfs，注意第一次bfs时不需要进行取模，直接将原数压入队列即可，如果取模的话会发生等于0的情况，这样结果就不对了。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int t;
typedef long long ll;
int yu[250];
const ll mod=233;
struct data
{ll x;ll ci;
};
ll F (ll x)
{x%=mod;return (x*x*x+x*x)%mod;
}
ll G (ll x)
{x%=mod;return (x*x*x-x*x)%mod;
}
ll bfs(ll x,ll y)
{queue<data>q;data t;t.ci=0,t.x=x;q.push(t);while (!q.empty()){data now=q.front();q.pop();if(now.x==y){return now.ci;}data next;next.ci=now.ci+1;next.x=F(now.x);if(yu[next.x]==0){yu[next.x]++;q.push(next);}next.x=G(now.x);if(yu[next.x]==0){yu[next.x]++;q.push(next);}}return -1;
}
int main()
{scanf("%d",&t);while (t--){memset (yu,0,sizeof(yu));ll a,b;scanf("%lld%lld",&a,&b);if(a==b){printf("0n");}else if(b>=mod){printf("-1n");}else{printf("%lldn",bfs(a,b));}}return 0;
}