自动搬运

查看原文

来自洛谷，原作者为

	船酱魔王 如花美眷，似水流年

搬运于2025-08-24 23:06:19，当前版本为作者最后更新于2024-10-22 23:26:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

T3. iterative

题意回顾

$r \leftarrow r\lceil r \rceil$ 记为一次操作，对于 $r=x+0.5$（$x$ 是给定的非负整数）需要几次操作才能让 $r$ 变成整数？

分析

若 $r=x+0.5$，则 $r'=r\lceil r \rceil=(x+1)(x+0.5)=x^2+1.5x+0.5$，设仍有 $r'=x'+0.5$，即 $x'=x^2+1.5x$。

设 $x$ 中含有的 $2$ 的因子个数为 $v(x)$，则若 $v(x)=0$，则 $x^2+1.5x+0.5$ 为整数；若 $v(x)>0$，则 $x'=x^2+1.5x$ 为整数，此时 $2^{v(x)}|x^2$，而 $2^{v(x)}|1.5x$ 不成立，因此 $v(x^2+1.5x)=v(1.5x)=v(x)-1$。

因此答案为 $v(x)+1$。

AC 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int T;
long long n;
int main() {
	cin >> T;
	for(int ti = 1; ti <= T; ti++) {
		cin >> n;
		for(int i = 1; i <= 64; i++) {
			if(n % 2 != 0) {printf("%d\n", i), n = -1; break;}
			else n /= 2;
		}
		if(n != -1) printf("NO!\n");
	}
	return 0;
}