数学是好的——数学老师
在信息学中,数学依然重要!!!
为肾膜?
蒟蒻:我都知道
看看历年的曾题:
NOIP2017 D1T1 小凯的疑惑
不定方程大佬(nao)一算,
a*b-a-b
得解!!!
AK*1,MARK+=100;
NOIP2016 D2T1 组合数问题
组合数学的递推+前缀和=>AK*2,MARK+=100;
虽然我听大佬说这题这么解。
NOIP2014 D2T3最后一道
质数筛法+简(du)单(liu)高精=>AK*3,MARK+=100;
还有很多:
计算系数,同余方程,转圈游戏······
~~~~~~~~~~~~~~~~~~~~
几乎每一届NOIP都有数学。
~~~~~~~~~~~~~~~~~~~~
数学老师说:数学是好的。
先把他请出去,这是信息教室。
而且,数学是比较好理解的算法之一,他包含了:质数,质数筛法,最大公约数(gcd),最小公倍数(lcm),欧拉函数,欧几里得算法,中国剩余定理,组合数学······
其实,你有一定的数学基础时,大概一天就能把这些算法摸一遍。
今天,我们先来讲质数,质数筛法,互质以及欧拉函数。
~~~~~
质数
~~~~~
只有1和它本身为因数的数叫质数。
特别地,1不是质数。
合数:除1和质数以外的正整数叫合数。
常识:100以内有25个质数。
——————
质数判定
——————
在放代码之前,我们先举几个栗子。
15。
我们手判质数会这样:(假设我们不知道它是不是)
15/2=7······1,
15/3=5
SO
15不是质数。
77.
手判质数:
77/2=38······1
77/3=25······2
······
77/7=11
SO
77也不是质数。
13.
13/2=6······1
13/3=4······1
13/4=3······1
ceil(sqrt(13))(根号13取上整)=4,
若13/2,3,4除不尽,13就是质数。
为什么呢?
蒟蒻:13本来就是质数。
好。来证明一下:
若x是合数,设它的一个因数为a,则x/a必是它的因数。
所以,只要算sqrt(x)就可以了。
code:
1 bool prime(int x) 2 { 3 if(x<=1) return 0; 4 if(x==2) return 1; 5 for(int i=2;i<=sqrt(x);i++) 6 { 7 if(x%i==0) 8 return 0; 9 } 10 return 1; 11 }
质数也有筛法,普通暴力筛我就不讲了,就是一个一个判。
我们要讲到的事线性筛,又叫欧拉筛法。
从 2 开始枚举当前数 i,去掉 i×p 这个合数,其中 p 是质数,且 p<i。 每个合数只会被其最小的质因子筛去,所以总的复杂度是线性的。
这就是它叫线性筛的原因。
我们先来看代码:
code:
1 memset(check,0,sizeof(check));//标记 2 int tot = 0;//质数个数 3 for(int i=2;i<=n;i++) 4 { 5 if(!check[i])//i没有别删去,则他是质数 6 { 7 prime[++tot]=i; 8 } 9 for(int j=1;j<=tot;j++)//去除i的倍数 10 { 11 if(i*prime[j]>n)//超过n,退出 12 { 13 break; 14 } 15 check[i*prime[j]]=1;//划去合数 16 if(i%prime[j]==0) 17 { 18 break;//合数被最小因子划去 19 } 20 } 21 }
理解 i % prime[j] == 0 是关键
原理:
1、任何一个合数都可以表示成一个质数和一个数的成绩
2、假设A是一个合数,且A=x*y,这里x也是一个合数,那么有:
A=x*y(假设x是合数,y是质数)
x=a*b(假设a是质数,则a<x --> a<y)
A=a*b*y=a*Z (Z=b*y)
3、即一个合数x与一个质数y的乘积能表示成一个更大的合数Z和一个更小的质数a乘积表示
所以对于当前i,若i % prime[j] == 0 --> i = prime[j] * x;
所以对于之后的任意数 i * prime[j+1] = prime[j] * prime[j+1] * x = prime[i] * y
即对于之后的数,我们都能用prime[j] * 一个更大的数来筛去,所以这里不用重复筛了
由于每个数只可能被最小的素数筛掉,所以复杂度为O(n)。
~~~~~~~~~~~~~
欧拉函数
~~~~~~~~~~~~~
欧拉函数就是表示小于n的数中与n互质的数的个数
code:
1 int euler(int n){ 2 int ans = n; 3 for(int i = 2; i * i <= n; i ++){ 4 if(n % i == 0){ 5 n /= i; 6 ans = ans / i * (i-1); 7 while(n % i == 0){ 8 n /= i; 9 } 10 } 11 } 12 if(n > 1) ans = ans / n * (n - 1); 13 return ans; 14 }
计算方法
φ(n) = n*(1-1/p1)*(1-1/p2)...
其中pi表示的是n的各个质因子
直接枚举质因数计算
其实没啥技术含量。
自己看一看就好利。毕竟蒟蒻都看懂了嘛
今天的内容就到这,希望大家在做信息数学题时rp+++;