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

结论：

当 $k \ne 0$ 时，答案为 $k$ 的因子 $2$ 的数量 $+1$ ；
当 $k=0$ 时无解。

思路/证明：

根据题意，设第

n

次迭代后的

r

值为

r_n

，则不难想到以下结论：

初始的 $\lceil r\rceil$ 的值应为 $k+1$ ；
第一次迭代后 $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}

，不可能变成整数。

代码

CPP

#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 见祖宗。

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

文章操作

结论：

思路/证明：

代码

相关推荐

评论

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