WPOI R2 C 题解
船酱魔王
·
·
题解
T3. iterative
题意回顾
## 分析
若 $ 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 代码
```cpp
#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;
}
```