关于向上取整和向下取整知识整理

向下取整函数 $f\left(x\right)=\lfloor x\rfloor$f(x)=⌊x⌋ 是单调递增的 ，向上取整函数 $f\left(x\right)=\lceil x\rceil$f(x)=⌈x⌉也是单调递增的。

对任意整数n，

$\lceil \frac{n}{2}\rceil +\lfloor \frac{n}{2}\rfloor =n$⌈2n​⌉+⌊2n​⌋=n

$\lceil \frac{n}{b}\rceil =\lfloor \frac{n+b-1}{b}\rfloor$⌈bn​⌉=⌊bn+b−1​⌋​

对任意 实数 $x\ge 0$x≥0和整数 $a,b>0$a,b>0

$\lceil \frac{\lceil x/a\rceil }{b}\rceil =\lceil \frac{x}{ab}\rceil$⌈b⌈x/a⌉​⌉=⌈abx​⌉​

$\lceil \frac{\lceil x/a\rceil }{b}\rceil =\lceil \frac{x}{ab}\rceil$⌈b⌈x/a⌉​⌉=⌈abx​⌉​

$\lceil \frac{a}{b}\rceil \le \frac{a+b-1}{b}$⌈ba​⌉≤ba+b−1​

以上参考《算法导论》第三版

令 $f_n\left(x\right)=\lceil \frac{n}{x}\rceil ,x\in [1,n]$fn​(x)=⌈xn​⌉,x∈[1,n]，那么 $f_n\left(x\right)$fn​(x)的结果有 $O\left(\sqrt{n}\right)$O(n ​)种，取法如下：

1. 令 $i=n$i=n
2. 令 $last=\lceil \frac{n}{\lceil n/i\rceil }\rceil$last=⌈⌈n/i⌉n​⌉​ ，那么 $\lceil \frac{n}{i}\rceil$⌈in​⌉​ 是一个解，且该解对应的最小整数 $last$last​满足 $f\left(last\right)=\lceil \frac{n}{i}\rceil$f(last)=⌈in​⌉​
3. 令 $i=last-1$i=last−1​，如果 $i>0$i>0​返回第二步

代码表示：

int cdiv(int a,int b)// a/b的向上取整
{
    return (a+b-1)/b;
}
void work(int n)
{
    int tol=0;
    for(int i=n,last;i>0;i=last-1,tol++)
    {
        cout<<"f(x):"<<cdiv(n,i)<<endl;//print the solutions
        last=cdiv(n,cdiv(n,i));
    }
    cout<<"The number of solutions :"<<tol<<endl;
}
int main()
{
    int n;
    cin>>n;
    work(n);
}

令 $f_n\left(x\right)=\lfloor \frac{n}{x}\rfloor ,x\in [1,n]$fn​(x)=⌊xn​⌋,x∈[1,n]，那么 $f_n\left(x\right)$fn​(x)的结果有 $O\left(\sqrt{n}\right)$O(n ​)种，取法如下：

1. 令 $i=1$i=1
2. 令 $last=\lfloor \frac{n}{\lfloor n/i\rfloor }\rfloor$last=⌊⌊n/i⌋n​⌋，那么 $\lfloor \frac{n}{i}\rfloor$⌊in​⌋ 是一个解，且该解对应的最大整数 $last$last满足 $f\left(last\right)=\lfloor \frac{n}{i}\rfloor$f(last)=⌊in​⌋
3. 令 $i=last+1$i=last+1，如果 i<=n，则返回第二步

代码表示：

int fdiv(int a,int b)
{
    return a/b;
}
void work(int n)
{
    int tol=0;
    for(int i=1,last;i<=n;i=last+1,tol++)
    {
        cout<<"f(x):"<<fdiv(n,i)<<endl;//print the solutions
        last=fdiv(n,fdiv(n,i));
    }
    cout<<"The number of solutions :"<<tol<<endl;
}
int main()
{
    int n;
    cin>>n;
    work(n);
}