初等数论基础

前言

这篇博客是数论笔记的第0章，主要内容包括：整除概念，唯一分解定理，约数个数，约数和，筛质数，分解质因数,欧拉函数

一、整除与基本数学符号

1.1 整除定义与性质

$$如果n\%d==0,那么n是d的倍数，d是n的约数，即d能整除n，即为d|n$$

• 下面给出整除的一些性质

1. $$a|b,b|c=>a|c$$
2. $$a|b,a|c=>a|kb+lc$$
   整除是数论的基石

1.2 求和与连乘

1.2.1 求和

根据整除符号以及求和符号的学习尝试写出这个式子：
答案：

求和的三个性质：

注：以上三个性质在做杜教筛题目或者反演题目时经常使用。
注意！！！
$$\sum _{i=1}^{n}a\cdot b!=\sum _{i=1}^{n}a\cdot \sum _{i=1}^{n}b,建议笔算验证，除法同理$$

1.2.2 连乘

为更好理解连乘符号：给出
其实可以注意到连乘即是阶乘函数。

1.3 带余除法

特别的，如果a,b除以c的余数相等，则称a,b模c同余，记做a同余b（mod c）
即a%c==b%c,则a,b模c同余。

1.4 素数（质数）

1.4.1 试除法求素数

试除法原理：n是素数当且仅当它不能被任何一个小于sqrt(n)的素数整除，

bool isprime(int n)
{
	if(n<2) return false;
	for(int i = 2;i<=n/i;i++)
	{
		if(n%i==0) return false; 
	}
	return true;
}

1.4.2 线性筛质数

原理：每个数只被最小的质因子筛去，时间复杂度O(n)

const int N = 100010;
bool st[N];
int primes[N];
int cnt;
void get_primes(int n)
{//线性筛1~n的素数
	for(int i = 2;i<=n;i++)
	{
		if(!st[i])
		{
			primes[cnt++] = i;
		}
		for(int j = 0;j<cnt&&i*primes[j]<=n;j++)
		{
			st[i*primes[j]] = true;
			if(i%primes[j]==0)
				break;
		}
	}
}
//prime即是素数数组

小性质1：1~n的质数个数大约是$$\frac{n}{lnn}个$$
小性质2：第n个质数的大小大约是$$nlog(n)$$

1.4.3 素因数分解

对于一个整数n，把它分解成若干个质因数相乘。
例题一：链接
给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
code:

#include<bits/stdc++.h>
using namespace std;

int n;
int main()
{
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;
        for(int i = 2;i<=a/i;i++)
        {
            //由质因数分解定理知，N = p1^a1*p2^a2^...pk^ak一定有p1,p2...pk相互互质
            //那么a对i做除法过后，对其他质因数分解是不会产生影响的
            if(a%i==0)
            {
                int s = 0;
                while(a%i==0)
                {
                    a/=i;
                    s++;
                }           
                cout<<i<<" "<<s<<endl;
            }
        }
        if(a>1)  cout<<a<<" "<<1<<endl;
        cout<<endl;
    }
    return 0;
}

二、gcd,lcm与唯一分解定理

2.1 gcd与lcm

2.1 定义与性质

$$\begin{gathered} gcd(a,b)表示a和b的最大公约数，一般用(a,b)表示。 \\ lcm(a,b)表示a和b的最小公倍数，一般用[a,b]表示，易知 \\ lcm(a,b)=a/gcd(a,b)\ast b \end{gathered}$$
性质0：

性质1：

数学符号记为:a⊥b
性质2：

$$\begin{gathered} 注意一个有意思的性质：虽然1既不是合数也不是质数 \\ 但是gcd(1,1)=1 \end{gathered}$$

2.2 辗转相除法求gcd(a,b)

详细手写证明也可以看另一篇博客~初等数论基础全览
$$gcd(a,b)=gcd(b,a\%b)$$
证明：
$$\begin{array}{rlr}& 不妨设d=gcd(a,b),r=a\%b& \\ & 那么r=a-b\lfloor \frac{a}{b}\rfloor & \\ & 易知d|a,d|b,且\lfloor \frac{a}{b}\rfloor 是正整数& \\ & 不妨令k=\lfloor \frac{a}{b}\rfloor ,则r=a-bk& \\ & & \\ & 由d|a,d|b那么d|a-bq(q\in 任意正整数)& \\ & \therefore d|r,则有d|a,d|b,d|r& \\ & \therefore a和b的约数与b和r的约数相同& \\ & \therefore gcd(a,b)=gcd(b,r)=gcd(b,a\%b)& \end{array}$$

typedef long long ll;
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}

2.2 唯一分解定理（算术基本定理）

任何一个大于1 的数都可以被唯一分解成有限个质数乘积的形式。
即$$\begin{gathered} n=\prod _{i=1}^m{p}_i^{C_i}=p_1^{C_1}\times p_2^{C^2}\times ...\times p_m^{C_m} \\ 其中，p1,p2...pm均是质数，C1,C2...Cm均是正整数 \end{gathered}$$
$$例如36可以唯一分解成36=2^2\times 3^2$$

2.2 正确性证明

后续更新

三、约数

3.1 约数定义

约数，又称因数，我们说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。

3.2 约数个数

对于一个整数N可以由算术基本定理写成：
$$\begin{array}{rl}& N=p_1^{C_1}\times p_2^{C_2}\times ...\times p_m^{C_m}\\ & 而N的约数d同样也可以写成\\ & d=p_1^{{\beta }_1}\times p_2^{{\beta }_2}\times ...\times p_k^{{\beta }_k}\\ & 再由算术基本定理可以知道只要{\beta }_i不同\\ & 那么约数d就不同，所以n的约数个数与{\beta }_i\\ & 的选法是相等的\\ & 由乘法原理，设约数个数为ans\\ & 显然有ans=(C_1+1)(C_2+1)....(C_k+1)\end{array}$$

3.3 约数之和

$$\begin{gathered} 如果N=p_1^{c_1}\times p_2^{c_2}\times ...\times p_k^{c_k} \\ 则约数之和=(p_1^0+p_1^1+...+p_1^{c_1})\ast ...\ast (p_k^0+p_k^1+...p_k^{c_k}) \end{gathered}$$

四、欧拉函数

4.1 定义

由唯一分解定理：

则有：
$$\phi (N)=N\cdot (1-\frac{1}{p_1})\cdot (1-\frac{1}{p_2})....(1-\frac{1}{p_m})$$
关于证明后续更新~

由观察知：欧拉函数的值与N分解成的质因数的指数无关

欧拉函数筛法详见博客：积性函数与筛法求积性函数~
后续更新~

五、快速幂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qmi(ll a,ll b,ll p)
{
    ll res = 1%p;
    while(b)
    {
        if(b&1) res = res*a%p;
        b>>=1;
        a = a*a%p;
    }
    return res;
}
int main()
{
    ll n;
    cin>>n;
    while(n--)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        cout<<qmi(a,b,c)<<endl;
    }
    return 0;
}