首页 > 代码库 > cogs 2687. 讨厌整除的小明

cogs 2687. 讨厌整除的小明

☆   输入文件:ming.in   输出文件:ming.out   逐字节对比
时间限制:1 s   内存限制:256 MB

【题目描述】


小明作为一个数学迷,总会出于数字的一些性质喜欢上某个数字,然而当他喜欢数字k的时候,却十分讨厌那些能够整除k而比k小的数,认为那些数会分解数字k从而破坏掉k的美感……


有一天,他想:如果所有人都和自己一样,那么是不是喜欢两个含有倍数关系的不同数字的人就不能做朋友了?于是他想,至少用多少个集合,才能包括1到n的所有n个整数,使得所有存在倍数关系的两个不同数字在不同的集合里面?


小明脑子不好使,于是把问题交给了你。




【输入格式】

第一行一个数字q,表示询问次数

接下来q行,每一行一个数字n,表示问题中的n。


【输出格式】

共q行,每行一个数字,表示数字n对应的问题的答案。

【样例输入】

1
5

【样例输出】

3

【提示】


{1}{2,5}{3,4}


【来源】

QBXT春季训练营的二次测试T1 

 

这是什么原因,为什么这样可以:

 1 # include <cstdio>
 2 # include <iostream>
 3 # define ll long long
 4 
 5 using namespace std;
 6 
 7 inline ll get_num() 
 8 {
 9     ll k = 0, f = 1;
10     char c = getchar();
11     for(; !isdigit(c); c = getchar()) if(c == -) f = -1;
12     for(; isdigit(c); c = getchar()) k = k * 10 + c - 0;
13     return k * f;
14 }
15 
16 inline ll get_line(ll x) 
17 {
18     ll k = 1;
19     while(x >> 1) 
20     {
21         x >>= 1;
22         k++;
23     }
24     return k;
25 }
26 
27 int main() 
28 {
29     freopen("ming.in", "r", stdin);
30     freopen("ming.out", "w", stdout);
31     ll n = get_num();
32     while(n--) 
33     {
34         ll x = get_num();
35         printf("%lld\n", get_line(x));
36     }
37 }

 

cogs 2687. 讨厌整除的小明