出题人题解 | #函数的魔法#

原题解链接：https://ac.nowcoder.com/discuss/150263

时间复杂度预处理$O(233\ast 233\ast 233)O(233*233*233)$

单次查询$O(1)O(1)$

弗洛伊德处理$233\ast 232233*232$对之间的转换最短路。

先特判$AA$与$BB$是否相等，相等就是$00$,如果$AA$和$BB$不相等并且$BB$大于等于$233233$的话,就是无解。

如果$AA$小于$233233$，$BB$小于$233233$,直接查询弗洛伊德表。

如果$AA$大于等于$233233$的话我们要先使用$F(X)F(X)$和$G(X)G\; (X)$将$AA$变换一步,然后A的值就小于$233233$了，然后查弗洛伊德表，两者里选取优的方案。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<bits/stdc++.h>
#include<vector>
using namespace std;
int f(long long x)
{
	x%=233;
	return (x*x*x+x*x)%233;
}
int g(long long x)
{
	x%=233;
	return (x*x*x-x*x)%233;
}
int dp[240][240];
int main()
{
	for(int i=0;i<233;i++)
	{
		for(int j=0;j<233;j++)
		{
			dp[i][j]=0x3f3f3f;
		}
		dp[i][f(i)]=1;
		dp[i][g(i)]=1;
		dp[i][i]=0;
	}
	for(int i=0;i<233;i++)
	{
		for(int j=0;j<233;j++)
		{
			for(int k=0;k<233;k++)
			{
				if(dp[j][k]>dp[j][i]+dp[i][k]) dp[j][k]=dp[j][i]+dp[i][k];
			}
		}
	}
	int T;
	while(scanf("%d",&T)!=EOF)
	{
		while(T--)
		{
			long long a,b;
			scanf("%lld %lld",&a,&b);
			if(a==b) printf("0\n");
			else
			{
				if(b>=233) printf("-1\n");
				else
				{
					if(min(dp[f(a)][b],dp[g(a)][b])==0x3f3f3f) printf("-1\n");
					else printf("%d\n",min(dp[f(a)][b],dp[g(a)][b])+1);
				}
			}
		} 
	}
}