[筆記]關於數論函數在程式碼上的實現

有鑑於在題庫裡出現的各式各樣的數論(不是樹論喔)函數題目，決定整理一下數論函數的算法。

        數論函數是指只定義域在整數的函數，對應到的值域並不限於整數(甚至可以是複數)，但常遇的大多只在整數域取值，因此本篇著重在 

的數論函數。

        



    
關於數論函數還有一個定義：
        只要函數符合

          
       就稱積性函數。

事實上，歐拉函數和*除數函數就是積性函數。(詳細的數論函數介紹待補，這裡大致提他的性質)

對於積性的數論函數，我們可以先進行預處理，把所有的N都進行因數分解。

O(NlglgN)

#include<vector>
#define N 1000000
struct pair
{
    int prime;
    int alpha;
};
std::vector<int>nd[N];
for(int lx=0;lx<prime.size();lx++)
{
    int a=1;
    for(int p=prime[lx];p<=N;p*=prime[lx],a++)
    {
        for(int ly=1;ly*p<=N;ly++)
        {
            if(ly%prime[lx]==0) continue;
            nd[ly*p].push_back(new pair(prime[lx],a));
        }
    }
}

因此在每次詢問，都可以做到O(lgN)的複雜度。

但對於一些比較特別的積性函數，譬如歐拉函數、*Möbius函數：

歐拉函數在p^a的值可以用phi(p^(a-1))和p表示出來，則可以在建質數表時以O(N)的複雜度填好。

以下取Möbius函數做例子：

    vector<int>prime;
    bool seive[1000000];
    int mu[1000000];
    mu[1]=1;
    for(int lx=2;lx<1000000;lx++)
    {
        if(!seive[lx])
        {
            prime.push_back(lx);
            mu[lx]=-1;
        }

        for(int ly=0;lx*prime[ly]<1000000;ly++)
        {
            seive[lx*prime[ly]]=true;
            if(lx%prime[ly]==0)
            {
                mu[lx*prime[ly]]=0;
                break;
            }
            else
                mu[lx*prime[ly]]=-mu[lx];
        }
    }

附上另外一個特別的積性函數：除數和函數，建表O(NlgN)：

1 int d[N];

2 for(int lx=1;lx<N;lx++)

3     for(int ly=1;ly*lx<N;ly++)

4         d[lx*ly]+=lx;

(將會更新)

*除數函數：

*Möbius函數：