函数的魔法(flody算法

函数的魔法(flody算法

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

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

g()和f()变来变去就呢么几种情况,以g()金额f()建边,边长为1,即变化1次

直接flody遍历,找出最短次数

最后别忘了函数里面x要先取余,否则会段错误(runtime error)

ac:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int mp[1001][1001]={0};int g(ll x)
{x=x%233;//忘记取余,会出现段错误(runtime error)return (x*x*x-x*x)%233;
}int f(ll x)
{x=x%233;return (x*x*x+x*x)%233;
}int main()
{ll a,b;int t;scanf("%d",&t);for(int i=0;i<1000;i++)for(int j=0;j<1000;j++)mp[i][j]=99999;for(int i=0;i<=233;i++){a=g(i);b=f(i);mp[i][a]=1;mp[i][b]=1;}for(int k=0;k<=232;k++)for(int i=0;i<=232;i++)for(int j=0;j<=232;j++)mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);while(t--){scanf("%lld%lld",&a,&b);if(a==b){cout<<0<<endl;continue;}if(b>=233){cout<<-1<<endl;continue;}else{int x=f(a);int y=g(a);if(x==b||y==b)cout<<1<<endl;else {if(mp[x][b]==99999&&mp[y][b]==99999)cout<<-1<<endl;else cout<<min(mp[x][b]+1,mp[y][b]+1)<<endl;}}}return 0;
}

转载于:.html