题解：P11310 无穷的迭代器

DrDuck · 2025-01-13 11:50:38 · 题解

基本思路

首先对 k 进行分类讨论，如果 k=0，则 r=\frac{1}{2}，则此时不小于 r 的最小整数为 1，不管乘多少次结果都是 \frac{1}{2}，此时可以直接输出NO!。

如果 k \ne 0 呢？我们直接按照题意来模拟，设分子为 t，由于分母恒等于 2，那么原式就应当乘上 \lfloor \frac{t}{2}\rfloor + 1，把这个结果直接乘到分子上，然后根据这个写一个循环，直到 t \mod 2 = 0就可以输出答案了。

还没完！注意数据范围！还是那句话，十年 OI 一场空，不开 long long 见祖宗！

CODE

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t, k;
signed main()
{
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cin >> k;
        if (k == 0)
        {
            cout << "NO!" << endl;
            continue;
        }
        int step = 0;
        k = k * 2 + 1;
        while (k % 2)
        {
            k *= (k / 2 + 1);
            step++;
        }
        cout << step << endl;
    }
    return 0;
}

拒绝抄袭！