定制开发板_广安网站制作设计_优化大师是什么软件_软文推广的100个范例

原题

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();}
}