[Algo Beat Contest 001 E] Experiments on Collatz 官方题解

joe_zxq · 2024-11-03 21:44:42 · 题解

出题人确实对角谷猜想很感兴趣呢。希望总有一天这个数学谜题被解开。

Part 1 - 预处理函数值

首先，可以很容易用递归暴力一一求解出所有的函数值，但是这样的效率显然很低，因为相同的函数值可能会在求解过程中被计算多次。

于是考虑记忆化剪枝优化。对于小于等于 x \le 10^7 的 f(x) 可以记忆化，用数组存储。那对于一些计算过程中出现的 x 很大的函数值的该怎么办呢？注意到这类的 x 出现次数较少，不会太多地被重复计算，于是可以直接暴力解决。

以上可以在一秒内处理。

Part 2 - 第一种询问

这个非常简单啦，直接进行预处理即可。

Part 3 - 第二种询问

这个可以考虑预处理前缀积，令 P_x 表示 \prod\limits_{i=1}^{x} f(i)，则 \prod\limits_{i=l}^{r} f(i)=\frac{P_r}{P_{l-1}}。由于需要取模，根据费马小定理，改除法为乘逆元即可。

Part 4 - Code

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int q, dp[10000005], ans[10000005];
ll pre[10000005], mn = 2e9;
const int mod = 1145141923;

ll qp(ll x, ll y) {
    if (y == 0) {
        return 1;
    }
    ll res = qp(x, y / 2);
    res *= res;
    res %= mod;
    if (y % 2) {
        res *= x;
        res %= mod;
    }
    return res;
}

int f(long long x) {
    if (x == 1) {
        return dp[x] = 0;
    }
    if (x <= 10000000 && dp[x]) {
        return dp[x];
    }
    if (x % 2 == 0) {
        ll res = f(x / 2) + 1;
        if (x <= 10000000) {
            dp[x] = res;
        }
        return res;
    } else {
        ll res = f(x * 3 + 1) + 1;
        if (x <= 10000000) {
            dp[x] = res;
        }
        return res;
    }
}

int inv(int x) {
    return qp(x, mod - 2);
}

int main() {

    ans[0] = 1;
    pre[0] = pre[1] = 1;
    for (int i = 1; i <= 10000001; i++) {
        dp[i] = f(i);
        ans[i] = 2e9; 
        if (i != 1) {
            pre[i] = pre[i - 1] * dp[i];
            pre[i] %= mod;
        }
    }
    for (int i = 1; i <= 10000000; i++) {
        ans[dp[i]] = min(ans[dp[i]], i);
    }
    for (int i = 10000000; i >= 0; i--) {
        ans[i] = min(ans[i], ans[i + 1]);
    }
    cin >> q;
    for (int i = 1, t, x, y; i <= q; i++) {
        cin >> t;
        if (t == 1) {
            cin >> x;
            cout << ans[x] << endl;
        } else {
            cin >> x >> y;
            if (x == 1) {
                cout << 0 << endl;
            } else {
                cout << pre[y] * inv(pre[x - 1]) % mod << endl;
            }
        }
    }

    return 0;
}