函数的魔法（水）

函数的魔法（水）

链接：
来源：牛客网
 

一位客人来到了此花亭，给了女服务员柚一个数学问题：我们有两个函数，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.

思路：

这道题很明显写个bfs就出了。奈何我取余的地方以前也一直没有注意过，导致细节使得出越界等等的错误。

总结一下就是，遇到各种很大的数相乘完了相加，例如：

a*a*a+a*a,那么取余操作就要变成,假设模233：

（（（a%233）*（a%233）*（a%233））%233+（（a%233）*（a%233））%233）%233

如果中间是减号，那么后边还要加上余数，因为很明显，假设模完了之后可能前边的减后边的就减不了了，变成负数了。

例如：

a*a*a-a*a,那么取余操作就要变成,假设模233：

（（a%233）*（a%233）*（a%233））%233+（（a%233）*（a%233））%233+233）%233

emmmmmmmm~以前这种取余式子我都没注意过。。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int>PII;
LL a,b;
int flag;
int vis[250];
void BFS()
{memset(vis,0,sizeof(vis));queue<PII>q;q.push(PII(a,0));///这个地方a会很大，所以不标记了。以后下一步就小了再标记。while(!q.empty()){PII qq=q.front();q.pop();LL u=qq.first;LL v=qq.second;if(u==b){cout<<v<<endl;flag=1;break;}LL uu,vv;vv=v+1;long long m=u%233;long long p1=((m*m*m)%233+(m*m)%233)%233;long long p2=((m*m*m)%233-(m*m)%233+233)%233;if(!vis[p1]){vis[p1]=1;q.push(PII(p1,vv));}if(!vis[p2]){vis[p2]=1;q.push(PII(p2,vv));}/*以前我是这么写的。。。uu=(u*u*u+u*u)%233;if(!vis[uu]){q.push(PII(uu,vv));vis[uu]=1;}LL uu2;uu2=(u*u*u-u*u)%233;if(!vis[uu2] ){q.push(PII(uu2,vv));vis[uu2]=1;}*/}
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%lld%lld",&a,&b);flag=0;if(a==b){printf("0n");continue;}if(b>=233)printf("-1n");else{BFS();if(flag==0){printf("-1n");}}}return 0;
}