原题
B. Brightness Begins
解析
Hint 1
第 i 个灯泡最终状态与 n 的大小无关
Hint 2
第 i 个灯泡最终状态与 i 的约数数量的奇偶性相关
Solution
对任意灯泡 i , 它的最终状态由其约数数量的奇偶性相关, 如果 i 有偶数个约数, 那么会是亮的, 否则会是暗的. 换句话说, 如果 i 不是一个完全平方数, 这个灯泡就会是亮的, 否则就是暗的.
因此问题转换成了找到第 k 个不是完全平方数的数这样一个数学问题.
可以用二分搜索 n - = k
也可以直接算 k + + 0.5
具体原因, 作者不是很清楚, 可能是某种数学推导证出来的, 因此作者打算熟记第k个不是完全平方数的数是k + + 0.5即可
sqrtl
当处理 long long 类型的求根时用 sqrtl 会更准确
代码
#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 200010;int n, m, k, q, ans;int a[N];void solve()
{cin >> k;cout << k + (long long) (sqrtl(k) + 0.5) << "\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while (T -- ){solve();}
}
