初等数论初步

初学数论

学得十分肤浅

判断质数

for(i = 2;i * i <= n;i++)
    if(n % i == 0)
    {
    	able = 1;
    	break;
    }  

判断1~n范围内的质数

inline void sieve(int x)
{
    int i,j;
    prime[1] = 1;
    for(i = 2;i * i <= x;i++)
        if(!prime[i])
            for(j = i * i;j <= x;j += i) prime[j] = 1;
}

然后学的是

整数的唯一分解

对于(forall)n

可表示为n = (sum_{i = 1,p|n}^{m_i}) (p^{w_i}_i)

//factorize
for(i = 2;i * i <= n;i++)
    {
        if(!vis[i])
        {
            p[++k] = i;
            while(n % i == 0)
                n /= i,w[k]++;
        }
    }
if(n != 1) p[++k] = n,w[k]++;

最小公倍数和最大公约数（gcd&&lcm）

对于(forall) a,b(in) Z

辗转相除法

inline LL gcd(LL a,LL b)
{
    if(a < b) exchange(a,b);
    if(b == 0) return a;
    return gcd(b,a % b);
}

还可以用整数的唯一分解来求

(gcd(a,b) = sum^{max(m_a,m_b)}_{i=1}p_i^{min(w_{ai},w_{bi})})

(lcm(a,b) = sum^{max(m_a,m_b)}_{i=1}p_i^{max(w_{ai},w_{bi})})

(a * b = gcd(a,b) * lcm(a,b)) 有重要作用

(forall)n的约数个数

d(n) = (prod_{i=1}^m(w_i+1))

乘法原理，+1指的指数取0

(forall)n的约数之和

s(n) = (prod_{i=1}^msum_{j=0}^{w_j}p_i^j)

清晰易懂 不解释

同余

a (equiv) b(mod m)

有性质
1: a (equiv) b(mod m) (Rightarrow) b (equiv) a(mod m)

2: a (equiv) b(mod m) , b (equiv) c(mod m)(Rightarrow) a (equiv) c(mod m)

3: a (equiv) b(mod m) (Leftrightarrow) m|(a - b)

4: a (equiv) b(mod m) , n|m 那么 a (equiv) b(mod n)

欧拉函数

看看 这位帅哥叫欧拉（滑稽

(phi(n)) 小于n的正整数中与n互质的数的数目

(phi(n)) = n * (prod_{i=1}^m(1 - frac{1}{p_i}))

计算(phi(n))

inline int phi(int n)
{
    int i,res = n;
    for(i = 2;i * i <= n;i++)
    {
        if(n % i == 0)
            res = res / i * (i - 1);
        while(n % i == 0) n /= i;
    }
    if(n > 1) res = res / n * (n - 1);
    return res;
}

计算(phi(i))(1<=i<=n)

inline void sieve(int n)
{
    phi[1] = 1;
    int i,j;
    for(i = 2;i <= n;i++)
    {
        if(!vis[i])
        {
            prime[++pn] = i;
            phi[i] = i - 1;
        }
        for(j = 1;j <= pn&&prime[j] * i <= n;j++)
        {
            vis[prime[j] * i] = 1;
            if(i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                //注释1
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
			/*积性函数f(a*b) = f(a) * f(b)（gcd(a,b) = 1）
        	phi[prime[j] - 1] = prime[j] - 1(prime[j]为质数)
        	*/
        }
    }
}

注释1：phi[i * prime[j] = n * prime[j] * (prod_{i=1}^m(1 - frac{1}{p_i}))

费马小定理

若有质数p，gcd(p,a) = 1

则有 (a^{p-1}) (equiv) 1(mod p)

二次探测定理

(x^2) (equiv) 1(mod p)

当 p 为奇质数时

(x_1 = 1)，(x_2 = p - 1)

威尔逊定理

(p是质数Leftrightarrow (p - 1)! equiv -1(mod p))