首页 > ACM题库 > HDU-杭电 > hdu 3020 FunnyXEN待解决[解题报告]C++
2014
02-27

hdu 3020 FunnyXEN待解决[解题报告]C++

FunnyXEN

问题描述 :

For any positive integer n, we define function F(n) and XEN(n).

For a collection S(n)={1,2,…,2n}, we select some numbers from it. For a selection, if each selected number could not be divided exactly by any other number in this selection, we will call the selection good selection. Further, we call a good selection best selection if the selection has more elements than any other good selection from S(n). We define F(n) the number of elements in the best selection from S(n). For example, n=2, F(n)=2. From the collection {1,2,3,4}, we can make good selection just like {2,3} or {3,4}, but we can’t make any larger selection. So F(2) = 2.

Then we pay attention to XEN(n). For every S(n), there are always some numbers could not be selected to make up any best selection. For instance, when n=2, 1 is always could not be chosen. What’s more, for every S(n), there is a number k which satisfies that all the number, from 0 to k, are always could not be chosen. Now we let XEN(n)=k:

n=2, F(n)=2, XEN(2)=1;
n=4, F(n)=4, XEN(4)=1.

You should write a program to calculate the value of F(n) and XEN(n) with a given number n.

输入:

Your program is to read from standard input.

There are multiple cases. For each case, one integer n (1 ≤ n ≤ 10^7) in a line.

输出:

Your program is to read from standard input.

There are multiple cases. For each case, one integer n (1 ≤ n ≤ 10^7) in a line.

样例输入:

2
4

样例输出:

2 1
4 1