Ubuntu 安裝記要

[給自己的筆記]
由於Ubuntu提供了一個圖形化的安裝界面
因此只大概紀錄一下安裝好後的軟體(分配70Gb)：


$ git
$ vim
$ python

還有關機是用：

$ sudo shutdown -h now  

AKS質數測試

[?]
=兒=

最近終於把AKS看完了@@ 下面的投影片是重點筆記，
應該有辦法幫助了解?
http://www.slideshare.net/mudream4869/aks-29609803

先備知識：分圓方程式在FINITE FIELD 上的性質、微積分

[筆記] 關於 A!/B! mod R

前幾天在競賽上碰到了一個問題的子問題：

在多次查尋下 使 單次查詢

 

複雜度達到O(1)

明顯的，是要建表、模逆表。

但模逆運算只在當模為質數時才是可行的(事實上，若模是質數，可以在O(2N)時間建完兩個表)，當模並非質數直接存表時，會發生悲劇。

因此，要設法把 A! 和 B! 提出一部分因數，使其與 R 互值。

藉由Legendre定理：

可以找出n!的p的次方數

定理相關細節可參考：Wiki

(1)建表、使用：

舉 R=pq 為例：

要建的表是：

Trivial(讀者自己想XD):

因此，便可以在O(1) 時間內取得

進而快速求得：

(2)遞推關係：

程式碼：

[待補]

建表時間大致為O(RlogR)

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

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

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

的數論函數。

        



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

          
       就稱積性函數。

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

對於積性的數論函數，我們可以先進行預處理，把所有的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函數：