#P6824. [2019年广州]猜想

    ID: 6656 传统题 1500ms 512MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>难度分类提高+/省选-模拟与实现技巧预计算转移高精度乘法直接模拟CF2300

[2019年广州]猜想

猜想

题目描述

给定一个正整数 nn,定义变换

$$f(n)=\begin{cases} n/2,&n\text{ 为偶数},\\ 3n+1,&n\text{ 为奇数}. \end{cases}$$

角谷猜想认为,对每个正整数反复进行这一变换,最终都会得到 11。

小 D 写出了一个用二进制表示的大整数 nn,想验证它。请按原题定义,求最小的正整数 kk,使得

f(k)(n)=1,f^{(k)}(n)=1,

其中 f(1)(n)=f(n)f^{(1)}(n)=f(n),f(k)(n)=f(f(k−1)(n))f^{(k)}(n)=f\bigl(f^{(k-1)}(n)\bigr)。每次除以 22 或执行一次 3n+13n+1 都分别计作一次变换。

输入格式

一行一个二进制正整数 nn。

输出格式

输出一行一个十进制整数,表示最小的正整数 kk。

样例 1 输入

1010

样例 1 输出

6

样例 1 解释

输入表示十进制的 1010,变换过程为

10→5→16→8→4→2→1,10\to5\to16\to8\to4\to2\to1,

共进行 66 次变换。

样例 2、3

原题面分别引用 conj/conj2.in、conj/conj2.ans 和 conj/conj3.in、conj/conj3.ans。当前本地附件未包含这些公开样例文件。

数据范围与子任务

记 ll 为输入二进制数的位数。所有数据满足 1≤l≤2×1051\le l\le2\times10^5,最高位为 11,其余 l−1l-1 位使用 std::mt19937 随机生成。

子任务 分值 附加限制
1 2020 l≤100l\le100
2 l≤1000l\le1000
3 1515 l≤5000l\le5000
4 2525 l≤5×104l\le5\times10^4
5 2020 无