数論の上方修正と下方修正に関する知識整理

アップとダウンに関する知識の整理
下向き整列関数f(x)=⌊x⌋f(x)=lfloor xrfloor f(x)=⌊x⌋は単調に増加し,上向き整列関数f(x)=⌈x⌉f(x)=lceil xrceil f(x)=⌈x⌉も単調に増加する.
任意の整数nに対して、
⌈ n 2 ⌉ + ⌊ n 2 ⌋ = n\lceil\frac{n}{2}\rceil+\lfloor\frac{n}{2}\rfloor=n ⌈2n​⌉+⌊2n​⌋=n
⌈ n b ⌉ = ⌊ n + b − 1 b ⌋ ​\lceil\frac{n}{b}\rceil=\lfloor\frac{n+b-1}{b}\rfloor​ ⌈bn​⌉=⌊bn+b−1​⌋​
任意の実数x≧0 xge 0 x≧0と整数a,b>0 a,b>0 a,b>0 a,b>0
⌈ ⌈ x/a ⌉ b ⌉ = ⌈ x a b ⌉ ​\lceil\frac{\lceil x/a\rceil}{b}\rceil=\lceil\frac{x}{ab}\rceil​ ⌈b⌈x/a⌉​⌉=⌈abx​⌉​
⌈ ⌈ x/a ⌉ b ⌉ = ⌈ x a b ⌉ ​\lceil\frac{\lceil x/a\rceil}{b}\rceil=\lceil\frac{x}{ab}\rceil​ ⌈b⌈x/a⌉​⌉=⌈abx​⌉​
⌈ a b ⌉ ≤ a + b − 1 b\lceil\frac{a}{b}\rceil\le\frac{a+b-1}{b} ⌈ba​⌉≤ba+b−1​
以上『アルゴリズム導論』第3版を参考にする
f n(x)=⌈n x⌉,x∈[1,n]f_n(x)=lceilfrac{n}{x}rceil,xin[1,n]fn(x)=⌈xn⌉,x∈[1,n],ではf n(x)f_n(x)fn(x)の結果はO(n)O(sqrt n)O(n)種であり、取り方は以下の通りである.

i=n i=n i=n

令l a s t=そしてこの解に対応する最小整数l a s t last lastはf(l a s t)=⌈n i⌉f(last)=lceilfrac{n}{i}rceil f(last)=⌈in⌉

を満たす.

は、i=l a s t−1 i=last−1 i=last−1とし、i>0 i>0 i>0が第2のステップ

に戻る場合、
コード表示:

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(x)=⌊n x⌋,x∈[1,n]f_n(x)=lfloorfrac{n}{x}rfloor,xin[1,n]fn(x)=⌊xn⌋,x∈[1,n],ではf n(x)f_n(x)fn(x)の結果はO(n)O(sqrt n)O(n)種であり、取り方は以下の通りである.

令i=1 i=1 i=1 i=1

令l a s t=⌊n/i a s t last last満足f(l a s t)=⌊n i⌋f(last)=lfloorfrac{n}{i}rfloor f(last)=⌊in⌋

は、i=l a s t+1 i=last+1 i=last+1とし、i<=n i<=n i<=nであれば、第2のステップ

に戻る.
コード表示:

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