【LGR-208-Div.3】T3 P11310 无穷的迭代器 题解

· · 题解

结论：

思路/证明：

根据题意，设第 n 次迭代后的 r 值为 r_n，则不难想到以下结论：

  1. 初始的 \lceil r\rceil 的值应为 k+1；
  2. 第一次迭代后 r_1=(k+\frac{1}{2})(k+1)=k^2+ \frac{3}{2}k+ \frac{1}{2}。

所以当初始的 k 就是奇数时，原式的值为整数，即只需一次迭代即可使 r 成为整数。

那么当 k 为偶数时，原式中的 \frac{3}{2}k 一项为整数；又因为 k^2 必定为整数，所以原式的值依旧可以写成“一个整数 +\frac{1}{2}”的形式。这样就可以继续使用结论二中的式子继续往后推。

于是我们设这个整数为 k_1，并将 n 次迭代后得到结果的整数部分设为 k_n。则转移式为：

k_n=k_{n-1}^2+ \frac{3}{2}k_{n-1} r_n=k_n+\frac{1}{2}

不难想到，当 k_{n-1} 为奇数，且 r_{n-1} 值依旧不是整数时，r_n 的值即为整数，n 就是答案。

观察第一个式子，因为在得到答案前，k_{n-1} 一直是偶数，故该式子的奇偶性仅取决于 \frac{3}{2}k_{n-1} 的奇偶性。若它的值为奇数，说明 k_{n-1} 的因子 2 的数量仅为 1。

我们发现：\frac{3}{2}k_{n-1} 的因子 2 的数量比 k_{n-1} 少 1。也就是，第次 n 迭代会使 k_n 的因子 2 的数量 -1。

回到初始的 k，思路就出来了。若 k 有 a 个因子 2，则 k_a 为奇数，r_{a+1} 的值为整数，答案就是 a+1。

无解的情况很好想到：k=0，则 r 永远等于 \frac{1}{2}，不可能变成整数。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,k; 
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>k;
        if(k==0){
            cout<<"NO!\n";
            continue;
        }
        ll n=0;
        while(!(k&1))//k除以几次2后变成奇数，就有几个因子2
        {
            k/=2;
            n++;
        }
        cout<<n+1<<endl;
    }
    return 0;
}

提醒：不开long long 见祖宗。