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

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

链接

[]

题意

题目描述
一位客人来到了此花亭，给了女服务员柚一个数学问题：我们有两个函数，F(X)函数可以让X变成（XXX+XX）mod 233。G(X)函数可以让X变成（XXX-XX）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变成(222+22)mod 233=12。然后我们再将12通过G(X)，变成(121212-1212)mod 233=186

分析

floyd的应用，看代码就知道了

代码

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=233;
int dp[310][310];
int t,a,b,cnt,n;
int f(int x){x%=mod; return (x*x*x+x*x)%mod;
}
int g(int x){x%=mod; return (x*x*x-x*x)%mod;
}
void init()
{memset(dp,inf,sizeof(dp));for(int i=0; i<mod; i++){dp[i][f(i)]=1;dp[i][g(i)]=1;dp[i][i]=0;}for(int k=0; k<mod; k++)for(int i=0; i<mod; i++)for(int j=0; j<mod; j++)if(dp[i][k]!=inf&&dp[k][j]!=inf)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
int main(){scanf("%d",&t);init();
//  for(int i=0; i<mod; i++){
//      for(int j=0; j<mod; j++)
//      cout<<dp[i][j]<<' ';
//      cout<<endl;
//  }
// while(t--){scanf("%d%d",&a,&b);if(a==b) printf("0n");else if(b>=mod) printf("-1n");else{if(a>=mod){//  cout<<1<<endl;cnt=1;n=f(a);a=g(a);if(dp[a][b]<inf||dp[n][b]<inf){cnt+=min(dp[a][b],dp[n][b]);printf("%dn",cnt);}else printf("-1n");}else{//cout<<2<<endl;if(dp[a][b]!=inf) printf("%dn",dp[a][b]);else printf("-1n");}}}return 0;
}

转载于:.html