数论主要研究整数的性质。需要关注的是一些特殊的数，如质数，素数，最大公约数，最小公倍数等等，以及相应的欧几里得算法，和各种筛法，欧拉函数，积性函数等等等等。。。。。。。
可以通过欧几里得算法来算出两个正整数a，b的最大公约数。
复杂度：
O
(
l
o
g
(
m
a
x
(
a
,
b
)
)
O(log(max(a,b))
O(log(max(a,b))
代码如下（示例）：
int gcd(int a, int b){
return b == 0? a : gcd(b,a%b);//b==0 是递归的边界条件
}
下面是该程序的运算过程：
也可以直接调用库函数__gcd(a,b);
素数只有：素数它本身和1。判断一个数是否是素数只需检查 2 ~ /
(
n
)
\sqrt(n)
(
n)内的整数是否存在有能整除这个数的数就能判断这个数是不是素数。
复杂度：
O
(
(
n
)
)
O(\sqrt(n))
O((
n))
代码如下（示例）：
bool is_prime()
{
for(int i=2;i*i<=n;i++)
{
if(n%i==0)return false;
}
return n!=1;
}
n内的素数的总数大概是 n / l n ( n ) n/ln(n) n/ln(n)个
用于高效去对多个整数进行素数检测（素数的个数<=
1
0
6
10^6
106)
2 ~ n的数写入数组，之后找到最小并且没有被划去的数，之后将在2 ~ n之间这个数的倍数划去，以此枚举n以内的素数。
复杂度：
O
(
n
l
o
g
(
l
o
g
(
n
)
)
)
O(nlog(log(n)))
O(nlog(log(n)))
代码如下（示例）：
#define MAX_N 1000010
int prime[MAX_N];
bool is_prime[MAX_N+1];
int sieve(int n)
{
int p=0;
for(int i=0;i<=n;i++) is_prime[i]=true;
is_prime[0]=is_prime[1]=false;
for(int i=2;i<=n;i++)
{
if(is_prime[i])
{
prime[p++]=i;
for(int j=2*i;j<=n;j+=i)is_prime[j]=false;
}
}
return p;
}
在区间[a,b)上 （a<b<=
1
0
12
10^{12}
1012,b-a<=
1
0
6
10^6
106)
用埃氏筛法算出[2,
(
b
)
\sqrt(b)
(
b)]的质数，同时划去[a,b)中这个质数的倍数。
代码如下（示例）：
#define MAX_L 1000010
#define MAX_SQRT_B 1000010
typedef long long int ll;
bool is_prime[MAX_L];
bool is_prime_small[MAX_SQRT_B];
void segment_sieve(ll a,ll b){
for(int i=0;(ll)i*i<b;i++)is_prime_small[i]=true;
for(int i=0;i<b-a;i++)is_prime[i]=true;
for(int i=2;(ll)i*i<b;i++)
{
if(is_prime_small[i]){
for(int j=2*i;(ll)j*j<b;j+=i){is_prime_small[j]=false;}
for(ll j=i*max(2LL,(a+i-1)/i);j<b;j+=i)is_prime[j]=false;
}
}
}
埃氏筛法在筛选时有重复，如6它被素数2和素数3都筛过，像这样的数有很多，而欧拉筛法不会。
int prime[maxn];
int is_prime[maxn];
void Prime(){
mem(is_prime,0);
mem(prime, 0);
for (int i = 2;i <= maxn; i++) {
if (!is_prime[i]) {
prime[++prime[0]] = i; //纪录素数， 这个prime[0] 相当于 cnt，用来计数
}
for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {
is_prime[i*prime[j]] = 1;
if (i % prime[j] == 0) {
break;
}
}
}
}
裴蜀定理
若a，b是整数，且gcd(a,b)=g，那么对于任意的整数x，y，ax+by=m中的m一定是g的倍数。反之ax+by=m有解，m一定是g的倍数。
它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1。
扩展欧几里德算法这个算法原理如下：
g
c
d
（
a
,
b
）
=
g
c
d
(
b
,
a
m
o
d
b
)
;
gcd（a,b）=gcd(b,a mod b);
gcd（a,b）=gcd(b,amodb);
g
c
d
(
a
,
b
)
=
a
x
1
+
b
y
1
(
裴
蜀
定
理
)
gcd(a,b)=ax_1+by_1(裴蜀定理)
gcd(a,b)=ax1+by1(裴蜀定理)
即
g
c
d
（
b
,
a
m
o
d
b
）
=
b
x
2
+
(
a
m
o
d
b
)
y
2
即gcd（b,a mod b）=bx_2+(a mod b)y_2
即gcd（b,amodb）=bx2+(amodb)y2
推导通解：
a
x
1
+
b
y
1
=
a
x
2
+
b
y
2
ax_1+by_1=ax_2+by_2
ax1+by1=ax2+by2
即
a
x
1
+
a
x
2
=
b
y
1
+
b
y
2
即ax_1+ax_2=by_1+by_2
即ax1+ax2=by1+by2
两
边
同
除
g
c
d
(
a
,
b
)
,
简
写
g
两边同除gcd(a,b),简写g
两边同除gcd(a,b),简写g//如果g=0，意味a=0 or b=0
(
a
/
g
)
(
x
1
+
x
2
)
=
(
b
/
g
)
(
y
1
+
y
2
)
,
有
因
为
互
素
，
所
以
(
x
1
+
x
2
)
一
定
是
（
b
/
g
）
的
倍
数
，
所
以
可
的
通
解
为
（
x
0
+
k
(
b
/
g
)
,
y
0
+
k
(
b
/
g
)
）
(a/g)(x_1+x_2)=(b/g)(y_1+y_2),有因为互素，所以(x_1+x_2)一定是（b/g）的倍数，所以可的通解为（x_0+k(b/g),y_0+k(b/g)）
(a/g)(x1+x2)=(b/g)(y1+y2),有因为互素，所以(x1+x2)一定是（b/g）的倍数，所以可的通解为（x0+k(b/g),y0+k(b/g)）
推导算法：
a
x
1
+
b
y
1
=
b
x
2
+
(
a
m
o
d
b
)
y
2
ax_1+by_1=bx_2+(amodb)y_2
ax1+by1=bx2+(amodb)y2
已
知
x
2
,
y
2
,
a
m
o
d
b
=
a
−
(
a
/
b
)
∗
b
,
代
入
已知x_2,y_2,amodb=a-(a/b)*b,代入
已知x2,y2,amodb=a−(a/b)∗b,代入
a
x
1
+
b
y
1
=
b
x
2
+
(
a
−
(
a
/
b
)
∗
b
)
y
2
=
ax_1+by_1=bx_2+(a-(a/b)*b)y_2=
ax1+by1=bx2+(a−(a/b)∗b)y2=
a
x
1
+
b
y
1
=
a
y
2
+
b
(
x
2
−
(
a
/
b
)
y
2
)
ax_1+by_1=ay_2+b(x_2-(a/b)y_2)
ax1+by1=ay2+b(x2−(a/b)y2)
x
1
=
y
2
,
y
1
=
(
x
2
−
(
a
/
b
)
y
2
)
x_1=y_2,y_1=(x_2-(a/b)y_2)
x1=y2,y1=(x2−(a/b)y2)
当
b
=
0
时
a
x
+
b
y
=
g
c
d
(
a
,
0
)
=
a
;
−
>
x
=
1
,
y
=
0
;
当 b=0时 ax+by=gcd(a,0)=a; ->x=1,y=0;
当b=0时ax+by=gcd(a,0)=a;−>x=1,y=0;//临界条件
//1.
void gcd(int a,int b,int& d,int& x,int& y)
{
if(!b){d=a;x=1;y=0;}
else {gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
//2.
int extgcd(int a,int b,int &x,int &y)//扩展欧几里得算法
{
int d=a;
if(b!=0)
{
d=extgcd(b,a%b,x,y);y-=(a/b)*x;
}
else
{
x=1;y=0;
}
return d;
}
费马小定理
如果p是一个质数，而整数a不是p的倍数，则有
a
p
−
1
≡
1
(
m
o
d
p
）
a^{p-1}≡1(mod p）
ap−1≡1(modp）。
逆元
类似倒数，
a
x
≡
b
m
o
d
m
;
a
c
≡
1
m
o
d
m
ax≡b mod m; ac≡1 mod m
ax≡bmodm;ac≡1modm; c就是a的逆元;
a
c
≡
1
m
o
d
m
等
价
a
c
=
1
+
m
k
ac≡1 mod m等价ac=1+mk
ac≡1modm等价ac=1+mk ac-mk=1,这就成了 扩展欧几里德算法。
int mod_inverse(int a,int b)
{
int x, y;
extgcd(a,m,x,y);
return (m+x%m)%m;
}
同余定理：
a mod b=c 则(a+b*k) mod b=c (k!=0)
(a+b) mod n=[(a mode n)+(b mod n)] mod n
(a-b) mod n=[(a mode n)-(b mod n)+n] mod n
a b mod n=(a mod n)(b mod n) mod n
注意乘法时可能会溢出所以要用long long int来保存中间结果
代码如下（示例）：
int mul_mod(int a,int b,int mod)
{
a%=mod;b%=mod;
return (int)(a*1LL*b)%mod;
}
x
n
=
（
(
x
2
)
2
)
.
.
.
\ x^ {n}=（(x^{2})^2)...
xn=（(x2)2)...。
复杂度：
O
(
l
o
g
(
n
)
)
O(log(n))
O(log(n))
代码如下（示例）：
typedef long long int ll;
ll mod_pow(ll x,ll n,ll mod)
{
ll res = 1;
while(n>0)
{
if(n&1) res=res * x % mod;//当n为奇数时
x=x*x%mod;
n>>=1;
}
return res;
}
C [ i ] [ j ] = C [ i − 1 ] [ j − 1 ] + C [ i − 1 ] [ j ] C[i][j]=C[i-1][j-1]+C[i-1][j] C[i][j]=C[i−1][j−1]+C[i−1][j]
n的正约数的个数：
(
a
1
+
1
)
(
a
2
+
1
)
.
.
(
a
n
+
1
)
(a1+1)(a2+1)..(an+1)
(a1+1)(a2+1)..(an+1)
欧拉筛法求1-n的k次方的约数个数之和
const int size=1e7+5;
bool prime[size];//is素数
int p[size];//素数
int sigma[size];//因质数个数
int tot=0;//素数个数
int k;//素数k次方
void init()
{
sigma[1]=1;
for(int i=2;i<size;i++) prime[i]=true;
for(int i=2;i<size;i++)
{
if(prime[i])
{
p[tot++]=i;
sigma[i]=k+1;
}
for(int j=0;j<tot&&p[j]*i<size;j++)
{
prime[i*p[j]]=false;
if(i%p[j]==0)
{
sigma[i*p[j]]=sigma[i]*2-sigma[i/p[j]];// 相当于
break;
}
else
{
sigma[i*p[j]]=sigma[i]*(k+1);// 相当于
}
}
}
}
算小于与n互素的整数个数用欧拉函数。
φ
φ
φ函数的值:
φ ( x ) = x ( 1 − 1 / p ( 1 ) ) ( 1 − 1 / p ( 2 ) ) ( 1 − 1 / p ( 3 ) ) … . . ( 1 − 1 / p ( n ) ) φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))…..(1-1/p(n)) φ(x)=x(1−1/p(1))(1−1/p(2))(1−1/p(3))…..(1−1/p(n)) 其中 p ( 1 ) , p ( 2 ) … p ( n ) p(1),p(2)…p(n) p(1),p(2)…p(n)为x的所有质因数;x是正整数; φ ( 1 ) = 1 φ(1)=1 φ(1)=1(唯一和1互质的数，且小于等于1)。注意：每种质因数只有一个。
条件概率：
P
（
B
∣
A
）
=
P
(
A
B
)
/
P
(
A
)
P（B|A）=P(AB)/P(A)
P（B∣A）=P(AB)/P(A)
全概率公式：
P
（
B
）
=
P
(
A
1
)
P
(
B
∣
A
1
)
+
P
(
A
2
)
P
(
B
∣
A
2
)
+
.
.
P（B）=P(A1)P(B|A1)+P(A2)P(B|A2)+..
P（B）=P(A1)P(B∣A1)+P(A2)P(B∣A2)+..