【每日一题】函数的魔法 题解

Description

一位客人来到了此花亭，给了女服务员柚一个数学问题：我们有两个函数，F(X)函数可以让X变成（XXX+XX）mod 233。G(X)函数可以让X变成（XXX-XX）mod 233，我们可以任意的对A使用F(X),和G(X)，问最少需要多少次使用这两个函数让A变成B。

Solution

由于模数只有233，我们进行函数变换后永远只能在 的区间里面，不妨用 的方法搜索出答案，由于 会对到过的点进行记录，不会重复走点，第一次到达的位置一定是最小的，最多搜索233次。所以时间复杂度为 。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
typedef long long ll;
struct node {
  ll val; 
    int step;
    node(ll _val = 0, int _step = 0):val(_val), step(_step){}
};
bool vis[255];
int bfs(ll a, ll b) {
    if(a == b) {
        return 0;
    }
    queue<node> q; q.push(node(a, 0));
    ll pre = a;
    while(!q.empty()) {
        auto tmp = q.front(); q.pop();
        if(tmp.val == b) return tmp.step;
        ll now = tmp.val;
        if(now < 255) {
            vis[now] = 1;
        }
        for(int i = 0; i < 2; i++) {
            if(!i) {
                int xx = ((now * now) % 233 * now + (now * now) % 233) % 233;
                if(!vis[xx]) {
                    q.push(node(xx, tmp.step + 1));
                } 
            } else {
                int xx = (((now * now) % 233 * now % 233 - (now * now) % 233) + 233) % 233;
                if(!vis[xx]) {
                    q.push(node(xx, tmp.step + 1));
                }
            }
        }
    }
    return -1;
}
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
  int T; cin >> T;
  while(T--) {
        ll a, b; cin >> a >> b;
        memset(vis, 0, sizeof(vis));
        cout << bfs(a, b) << '\n';
  }
  return 0;
}