数学专题1-阿里云开发者社区

开发者社区> 人工智能> 正文

数学专题1

简介: 数学是好的——数学老师 在信息学中,数学依然重要!!! 为肾膜? 蒟蒻:我都知道 看看历年的曾题: NOIP2017 D1T1 小凯的疑惑 不定方程大佬(nao)一算, a*b-a-b 得解!!! AK*1,MARK+=100;   NOIP2016 D2T1 组合数问题 组合数学的递推+前缀和=>AK*2,MARK+=100; 虽然我听大佬说这题这么解。

数学是好的——数学老师

在信息学中,数学依然重要!!!

为肾膜?

蒟蒻:我都知道

看看历年的曾题:

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+++;

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章