质数
定义
若一个数，只有一和它本身两个因子，那么这个数就是一个质数
判断一个数是不是质数的方法
试除法
bool pd(int x)
{
if(x<2) return 0;
for(int i=2;i<=sqrt（x）;i++)
{
if(x%i==0)
return 0;
}
return 1;
}
看着就知道这就是傻瓜思路,一个一个试,试到sqrt(x).(傻瓜思路不解释了)
如何筛出质数(用于预处理数组)
1.埃氏筛
利用已经筛出的素数去筛别的素数.
代码如下
int n,prime[N];
void p()
{
for(int i=2;i<=n;i++)
{
if(prime[i])
continue;
for(int j=2;i*j<=n;j++)
prime[i*j]=1;
}
return ;
}
2.欧拉筛
比线性筛的复杂度更低一点
每次只用一个数用小于当前这个数最小质因子的质数去筛其他数
代码如下
int n,prime[N],cnt;
bool vis[N];
void p()
{
for(int i=2;i<=n;i++)
{
if(!vis[i])
prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
}
当然不会上面两个你也可以一个个枚举然后试除
质因数分解
根据上面两个筛法,我们可以把一个数分解成几个质数次方的乘积.
约数
定义
若整数n可以被整数x整除,那么记x为n的约数.x|n.
求 N N N的正约数的集合
对于任意的
d
∣
n
d|n
d∣n，只要扫描
1
⋯
n
1\cdots\sqrt n
1⋯n
就能找到n的所有正约数。
代码如下
int factor[N] ,；
int tot = 0;
for(int i=1;i<=sqrt(n);i++)
{
if(n%i)
continue;
factor[++tot]=i;
if(i!=n/i)
factor[++tot]=n/i;
}
最大公约数
定义
若自然数 d d d同时是 a a a和 b b b的约数，则称 d d d是 a a a和 b b b的公约数
在所有的公约数中最大的一个就是最大公约数，记作 g c d ( a , b ) gcd(a,b) gcd(a,b)
最小公倍数
定义
若自然数 m m m同时是 a a a和 b b b的倍数，则成 m m m是 a a a和 b b b的公约数
在所有的公倍数中最小的一个就是最小公倍数，记住 l c m ( a , b ) lcm(a,b) lcm(a,b)
引理
l c m ( a , b ) ∗ g c d ( a , b ) = a ∗ b lcm(a,b)*gcd(a,b)=a*b lcm(a,b)∗gcd(a,b)=a∗b
证明
设 x = g c d ( a , b ) , a 0 = a x , b 0 = b x x=gcd(a,b),a_0=\frac{a}{x},b_0=\frac{b}{x} x=gcd(a,b),a0=xa,b0=xb
根据定义得
g
c
d
(
a
0
,
b
0
)
=
1
gcd(a_0,b_0)=1
gcd(a0,b0)=1
l
c
m
(
a
0
,
b
0
)
=
a
o
×
b
0
lcm(a_0,b_0)=a_o\times b_0
lcm(a0,b0)=ao×b0
所以
l
c
m
(
a
,
b
)
=
l
c
m
(
a
0
×
d
,
b
0
×
d
)
=
l
c
m
(
a
0
,
b
0
)
×
d
=
a
0
×
b
0
×
d
=
a
×
b
d
lcm(a,b)=lcm(a_0\times d,b_0\times d)=lcm(a_0,b_0)\times d=a_0\times b_0 \times d = \frac{a \times b }{d}
lcm(a,b)=lcm(a0×d,b0×d)=lcm(a0,b0)×d=a0×b0×d=da×b
证毕。
欧几里得算法
我们或许可以叫他辗转相除法？
任取
a
,
b
∈
N
,
b
≠
0
,
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
m
o
d
b
)
a , b \in N , b \ne 0, gcd(a,b) = gcd(b , a \mod b)
a,b∈N,b=0,gcd(a,b)=gcd(b,amodb)
就是这个式子，证明就略了
代码如下
int gcd( a , b )
{
return b ? gcd( b , a % b ) : a;
}
互质
定义
如果两个数的最大公约数为1，即
g
c
d
(
a
,
b
)
=
1
gcd(a,b)=1
gcd(a,b)=1,那么就称这两个数互质
对于三个数来说同理.
欧拉函数
定义
1
⋯
N
1\cdots N
1⋯N中与N互质的数的个数，被称为欧拉函数，记作
ϕ
(
N
)
\phi(N)
ϕ(N)
求法:在筛因数的时候顺便 求解
代码如下
int phi( int x )
{
int ans=x;
for(int i=2;i*i<=x;i++)
{
if(x%i) continue;
ans=ans/i*(i-1);
while(x%i==0)n/=i;
}
if(n>1)
ans=ans/n*(n-1);
return ans ;
}
性质
- ∀ n > 1 , 1 ⋯ n 中 与 互 质 的 数 的 和 为 n × ϕ ( n ) / 2 \forall n > 1 , 1\cdots n中与互质的数的和为n\times \phi(n) / 2 ∀n>1,1⋯n中与互质的数的和为n×ϕ(n)/2
- 若a,b互质，则 ϕ ( a b ) = ϕ ( a ) ϕ ( b ) \phi(ab)=\phi(a)\phi(b) ϕ(ab)=ϕ(a)ϕ(b)
就这就这,看完了的你不给个赞吗?
下面是同余时间!!!