OJ周赛第二场——简单问题

标签：周赛 OJ 10 第二场 int cin 整数 tie cout

简单问题  

问题描述 

给定一个正整数n，你需要找出最小的整数k，使得对于大小为k的集合{1,2,⋯,n}的任何子集T，存在两个不同的整数u,v∈T，u是v的一个因子。

 

输入 

第一行包含一个整数T（1≤T≤10^5）表示测试用例的数量。

接下来的T行每行包含一个整数n（2≤n≤10^9），描述一个测试用例。

输出 

对于每个测试案例，输出一行包含一个整数，表示答案。

 

输入例子 1 

4
2
3
4
5

输出例子 1

2
3
3
4

提示：

把问题转换成选最多的k的集合使得不存在互为因子，然后k+1就是本题答案。

那么显然选最大的n/2上取整的数。比如n=9，那么肯定最优是5，6，7，8，9。

结合本题题目，也可以从样例找到规律。

 

答案：

#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
cin >> n;
cout << (n + 1) / 2 + 1 << "\n";
}

return 0;
}

 

标签：周赛,OJ,10,第二场,int,cin,整数,tie,cout
From： https://www.cnblogs.com/hihopkc/p/16866100.html