NC21884. 函数的魔法
描述
输入描述
第一行输入一个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=186C++14(g++5.4) 解法, 执行用时: 65ms, 内存消耗: 1636K, 提交时间: 2018-12-28 19:26:13
#include<bits/stdc++.h>
#define inf 1000000007
using namespace std;
int d[1000][1000];
int main(){
for (int i=0;i<233;i++) for (int j=0;j<233;j++) d[i][j]=inf;
for (int i=0;i<233;i++){
d[i][(i*i*i+i*i)%233]=1;
d[i][(i*i*i-i*i)%233]=1;
}
for (int k=0;k<233;k++)
for (int i=0;i<233;i++)
for (int j=0;j<233;j++) if (d[i][k]+d[k][j]<d[i][j])
d[i][j]=d[i][k]+d[k][j];
int tt;scanf("%d",&tt);
for (;tt--;){
int a,b;scanf("%d%d",&a,&b);
if (a==b) puts("0");
else if (b>=233) puts("-1");
else if (d[a%233][b]==inf) puts("-1");
else printf("%d\n",d[a%233][b]);
}
}
C++11(clang++ 3.9) 解法, 执行用时: 48ms, 内存消耗: 2916K, 提交时间: 2020-02-27 13:16:14
#include<bits/stdc++.h>
#define inf 1000000007
using namespace std;
int d[1000][1000];
int main()
{
for(int i=0;i<233;i++)
for(int j=0;j<233;j++)
d[i][j]=inf;
for(int i=0;i<233;i++)
{
d[i][(i*i*i+i*i)%233]=1;
d[i][(i*i*i-i*i)%233]=1;
}
for(int k=0;k<233;k++)
for(int i=0;i<233;i++)
for(int j=0;j<233;j++)
if(d[i][k]+d[k][j]<d[i][j])
d[i][j]=d[i][k]+d[k][j];
int tt;
scanf("%d",&tt);
for(;tt--;)
{
int a,b;
scanf("%d%d",&a,&b);
if(a==b) puts("0");
else if(b>=233) puts("-1");
else if(d[a%233][b]==inf) puts("-1");
else printf("%d\n",d[a%233][b]);
}
}