【每日一题】12月15日题目精讲

题号 NC21884
名称 函数的魔法
来源 牛客练习赛35
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468

题解

假设我们用一个邻接矩阵来表示计算步骤， 到 连接一条有向边代表 可以经过一次计算得到 ，也就是说，对于 ， 到 以及 到 都连接一条有向边。这样就得到了一个 233*233 的邻接矩阵。
对于一个邻接矩阵而言，矩阵中的元素都是用0,1来表示是否联通的，或者说，代表有没有方法从走到。那么，就是表示从 走到 再走到 是否可行。可以发现， 其实就是统计用2步从 走到 的方法总数。
因此，可以预处理出 、 、…… 这些所有的邻接矩阵（很明显，最多计算232次就足够了）。之后每次询问的时候，复杂度在矩阵中遍历就可以了。
注意要特判两种情况：①a=b的时候，无论怎样直接输出0即可。②除第一种情况以外， 时显然无解，输出-1。
之后询问的时候可以用 和 在预处理得到的233个邻接矩阵中进行询问。
参考代码：

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
struct Matrix{
    int a[253][253];
};

long long f(long long x){
    return x*x*(x+1)%233;
}
long long g(long long x){
    return x*x*(x-1)%233;
}
Matrix f(Matrix a)
{
    int i,j,k;
    Matrix tmp;
    for(i=0;i<233;++i)
    {
        for(j=0;j<233;j++)
            if(a.a[i][j]==1)
        {
            tmp.a[i][f(j)]=1;
            tmp.a[i][g(j)]=1;
        }
    }
    return tmp;
}
  Matrix m[253];
int main()
{
    int i;
    for(i=0;i<233;i++)m[0].a[i][i]=1;
    for(i=1;i<=233;i++){
        m[i]=f(m[i-1]);
    }
    int t;
    cin>>t;
    while(t--){
        long long a,b;
        cin>>a>>b;
        if(a==b)cout<<"0"<<endl;
        else if(b>=233)cout<<"-1"<<endl;
        else{
            a%=233;
            for(i=1;i<=233;i++){
                if(m[i].a[a][b]==1)break;
            }
            if(i>233)cout<<-1<<endl;
            else cout<<i<<endl;
        }
    }
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目12月22日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴