首页 > > 程序设计 > C/C++ >

NOIP复习之1 数学数论

2018-09-18 06:25:32来源：博客园阅读 ()

noip一轮复习真的要开始啦！！！

大概顺序是这样的

1.数学

2.搜索贪心

3.数据结构

4.图论

5.dp

6.其他

　　　　　　　　　　　　　　　　数学

1.数论

数论被称为数学皇冠上的明珠，他的重要性主要在于它是其他学习的祖师，基本上什么代数问题都可以通过数论推导，其实有的图论也是（数学上）。

我们信息中的数论主要是说对整除同余的研究~~~~~~~

①：唯一分解定理与素数

这个之前我们先要讲素数（定义全部掠过）

素数筛法：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int prime[1000100],phi[1000100],n,m,k,l,a,b;
 6 bool isprime[1000100];
 7 void shai()
 8 {
 9     int sum=0;
10     memset(isprime,0,sizeof(isprime));
11     memset(prime,0,sizeof(prime));
12     for(int i=2;i<=n;i++)
13     {
14         if(!isprime[i])
15         {
16             prime[sum++]=i;
17             phi[i]=i-1;
18         }
19         for(int j=0;j<sum&&prime[j]*i<=n;j++)
20         {
21             isprime[prime[j]*i]=1;
22             if(i%prime[j]==0)
23             {
24                 phi[i*prime[j]]=phi[i]*prime[j];
25                 break;
26             }
27             else
28             {
29                 phi[i*prime[j]]=phi[i]*(prime[j]-1);
30             }
31         }
32     }
33 } 
34 int main()
35 {
36     phi[1]=1;
37     cin>>n;
38     shai();
39     for(int i=0;i<=n;i++)
40     cout<<phi[i]<<" ";
41     return 0; 
42 }

这里面也有一个叫phi的东西。。。我们一会再说。

筛好以后我们就可以根绝唯一分解定理分解素数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int prime[10000100],phi[10000100],cut[10000100][3],num=0,n,m,k,l,a,b;
 6 bool isprime[10000100];
 7 void shai()
 8 {
 9     int sum=0;
10     memset(isprime,0,sizeof(isprime));
11     memset(prime,0,sizeof(prime));
12     for(int i=2;i<=10000000;i++)
13     {
14         if(!isprime[i])
15         {
16             prime[sum++]=i;
17             phi[i]=i-1;
18         }
19         for(int j=0;j<sum&&prime[j]*i<=n;j++)
20         {
21             isprime[prime[j]*i]=1;
22             if(i%prime[j]==0)
23             {
24                 phi[i*prime[j]]=phi[i]*prime[j];
25                 break;
26             }
27             else
28             {
29                 phi[i*prime[j]]=phi[i]*(prime[j]-1);
30             }
31         }
32     }
33 } 
34 int main()
35 {
36     phi[1]=1;
37     shai();
38     cin>>m;
39     for(int i=0;i<=10000000;i++){
40         if(m==1)break;
41         while(m%prime[i]==0)m/=prime[i],cut[i][1]=prime[i],cut[i][2]++;
42     }
43     for(int i=0;i<=1000;i++){
44         if(cut[i][1]!=0)
45         cout<<cut[i][1]<<" "<<cut[i][2]<<endl;
46     }
47     return 0; 
48 }

省选之后我们发现o跟下n求一个数的唯一分解是不够的

于是就有了miller rabin。

这个东西是根据那个费马小定理（欧拉定理）的p为素数的条件进行的素数测试。

这个东西有个兄弟叫rho

这个东西是用来解决找合数因子的

把主程序里的不断除m改为知道miler检测到为素数为止。

好了那么我们就可以对10^18次方之内的进行分解了（noip只会考on）

那么有什么用呢？

我们把分解后的表示为π（ai^pi）

1.因子数：π（pi+1）；

2.因子和：这个很有意思：

ans=(1+p1^1+p1^2+......+p1^a1)(1+p2^1+p2^2+......+p2^a2)(1+p3^1+p3^2+......+p3^a3)......(1+pn^1+pn^2+......+pn^an)

=π(1-pi^ai)/(1-pi);

这个东西逆元就行。

②快速幂（模数的最广泛应用（二进制））

 1 //ksm
 2  #include<iostream>
 3  #include<cstdio>
 4  #include<algorithm>
 5  #include<queue>
 6  #include<stack>
 7  #include<fstream>
 8  #include<cstring>
 9  using namespace std;
10  #define ll long long
11  ll qpow(ll a,ll x)
12  {
13      ll base=a,ans=1;
14      for(;x>0;x>>=1)//简单办法 
15      {if(x&1)
16          ans*=base;//当为奇数叠加求解 
17          base*=base;
18      }
19      return ans;
20  } 
21   int main()
22  {
23      //freopen(".in","r",stdin);
24      //freopen(".in","r",stdin);
25      ll a,b;
26      cin>>a>>b;
27      cout<<qpow(a,b);
28      return 0;
29  }

这个东西根据费马小定理可以求逆元

方法是a^(mod-2)=a^(-1)mod mod;

快速乘其实是龟速乘

利用二进制实现调整中途溢出long long的膜意义下乘法

也是利用二进制表示

这样就可解决10^18次方的两个数在%意义下的乘法取模

（其实它是log length的复杂度，并不快，只是比n个相加取模要快（传统防止溢出）所以不是像noi2018龙和勇士那种问题不要乱用）

 1 #include<iostream>
 2 #define mod 1000000007
 3 #define ll long long
 4 using namespace std;
 5 ll ksc(ll a,ll b){
 6     ll ans=0,base=a;
 7     for(;b;b>>=1){
 8         if(b&1)ans=(ans+base)%mod;
 9         base=base*2%mod;
10     }
11     return ans;
12 }
13 ll a,b; 
14 int main(){
15     cin>>a>>b;
16     cout<<ksc(a,b);
17     return 0;
18 }

③exgcd gcd

gcd太熟悉了现打一个

1 long long gcd(long long a,long long b){
2     return !b?a:gcd(b,a%b);
3 }

exgcd也差不多 exgcd也可以求逆元的，这个定义式推。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 int gcd(int a,int b)
 6 {
 7     return b==0?a:gcd(b,a%b);
 8 }
 9 void exgcd(int a,int b,int &d,int &x,int &y)
10 {
11     if(!b){d=a;x=1;y=0;return ;}
12     exgcd(b,a%b,d,y,x);
13     y-=(a/b)*x;
14 }
15 int main ()
16 {
17     int m,n,k;
18     cin>>m>>n>>k;
19     int gc=gcd(n,m);
20     m/=gc;n/=gc;
21     k/=gc;
22     int x,y,d;
23     cout<<m<<"x+"<<n<<"y="<<gc<<endl;
24     exgcd(m,n,d,x,y);
25     cout<<x<<" "<<y<<endl<<d<<endl<<endl;
26     for(int i=1;i<=10;i++)
27     {
28         x+=(n)*i;
29         y-=(m)*i;
30         cout<<x<<" "<<y<<endl;
31     }
32     return 0;
33 }

④excrt。crt

excrt 在noip是在不大可能考，要考也是t3的最后一部分，毕竟noi t1难度不是盖的（当时本蒟蒻只拿了三十分那个题。。。。）

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<ctime>
 4 #include<cstdio>
 5 #include<cstring>
 6 using namespace std;
 7 long long m[100000],ma[100000],a[100000],c,mall=1,ansx;
 8 long long qpowmod(long long a,long long x,long long p)
 9 {
10     long long base=a,ans=1;
11     for(;x>0;x>>=1){
12         if(x&1)
13         ans*=base,ans%=p;
14         base*=base,base%=p;
15     }
16     return ans%p;
17 }
18 int main()
19 {
20     
21     cin>>c;
22     for(int i=1;i<=c;i++){
23         cin>>a[i]>>m[i];
24         mall*=m[i];
25     }
26     for(int i=1;i<=c;i++){
27         ma[i]=mall/m[i];
28     }
29     for(int i=1;i<=c;i++){
30         ansx+=a[i]*ma[i]*qpowmod(ma[i],m[i]-2,mall);
31         ansx%=mall;
32     }
33      
34     cout<<mall<<endl<<ansx<<endl;
35 }

excrt的话就是加一个exgcd就行。

另外我们需要利用bezout解决问题比如小凯的疑惑

几个简单而熟知的结论

(a,b)=(a+b,b)=(a-b,b)

ax+by=(a,b) x,y∈z

2.计算几何

计算几何noip要是考也是向量题，最多带个凸包。

①向量点积a2b1-a1b2

②凸包：这个东西在斜率优化那里有（那里是个上凸壳），大概是完全一样的。栈维护进出

保证点积>0

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cmath>
 5 using namespace std;
 6 struct node{
 7     double x,y;
 8 }p[10005],s[10005];
 9 int n;
10 double ans,mid;
11 double CJ(node a1,node a2,node b1,node b2)
12 {
13     return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
14 }
15 double dis(node p1,node p2)
16 {
17     return sqrt( (double)(p2.y-p1.y)*(p2.y-p1.y)*1.0+(double)(p2.x-p1.x)*(p2.x-p1.x)*1.0 );
18 }
19 bool cmp(node p1,node p2)
20 {
21     double tmp=CJ(p[1],p1,p[1],p2);
22     if(tmp>0) return 1;
23     if(tmp==0 && dis(p[0],p1)<dis(p[0],p2)) return 1;
24     return 0;
25 }
26 int main()
27 {
28     scanf("%d",&n);
29     for(int i=1;i<=n;++i)
30     {
31         scanf("%lf%lf",&p[i].x,&p[i].y);
32         if(i!=1&&p[i].y<p[1].y)
33         {
34             mid=p[1].y;p[1].y=p[i].y;p[i].y=mid;
35             mid=p[1].x;p[1].x=p[i].x;p[i].x=mid;
36         }
37     }  
38 
39     sort(p+2,p+1+n,cmp);
40     s[1]=p[1];
41     int tot=1;
42     for(int i=2;i<=n;i++)
43     {
44         while(tot>1&&CJ(s[tot-1],s[tot],s[tot],p[i])<=0) tot--;
45         tot++;
46         s[tot]=p[i];
47     }
48     s[tot+1]=p[1];
49     for(int i=1;i<=tot;i++) ans+=dis(s[i],s[i+1]);
50     printf("%.2lf\n",ans);
51     return 0;
52 }

3.递推，矩阵初步与数列

①几个有趣的特殊数列

②ologn求通项的几（两）种方法（noipt2t3）{

1.特征根

这个东西没有任何代码。。。就是求数列通项。

通过特征方程解出跟

然后带a1，a2，a3……an进去

可以看看这个

https://wenku.baidu.com/view/6e270e87284ac850ac024203.html

2.矩阵快速幂

这个十分好理解（在矩阵乘法理解的基础上）我们可以认为数列是一个行向量

而一个n阶递推数列对应一个列向量，所以因此我们就需要找到一个由前一个列向量递推到下一个的矩阵。

这个矩阵可以记一个结论

它是对于n阶矩阵 ai为系数

n*n大小

[a1,a2,a3,a4,……,an]

[10000000000……00]

[010000000……00]

[0010000000……00]

[00010000000……00]

[000010000000……00]

[0………………1]

然后矩阵快速幂！！！

就是矩阵乘法代替那个快速幂的乘就行

代码！！！

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 int n,k;
 6 struct mix{
 7     int a[105][105];
 8 };
 9 mix mx (mix a1,mix a2,int n)
10     {    
11         mix a3;int ans=0;
12         memset(a3.a,0,sizeof(a3.a));
13         for(int i=1;i<=n;i++)
14         for(int j=1;j<=n;j++)
15         {
16             ans=0;
17         for(int k=1;k<=n;k++)
18         {
19             ans+=a1.a[i][k]*a2.a[k][j];
20         }
21         a3.a[i][j]=ans; 
22         } 
23         return a3;
24     }
25 mix ksm(mix a,int x)
26 {
27     mix ans;
28     memset(ans.a,0,sizeof(ans.a));
29     for(int i=1;i<=n;i++)
30     ans.a[i][i]=1;
31     for(;x;x>>=1)
32     {
33         if(x&1)
34         mx(ans,a,n);
35         mx(a,a,n);
36     }
37     return ans;
38 } 
39 int main()
40 {
41     mix m1;
42     cin>>n>>k;
43     cout<<endl<<n<<endl<<k;
44     for(int i=1;i<=n;i++)
45     for(int j=1;j<=n;j++)
46     cin>>m1.a[i][j];
47         
48     mix m=ksm(m1,k);
49     for(int i=1;i<=n;i++)
50     {
51         cout<<endl;
52     for(int j=1;j<=n;j++)
53         {
54             cout<<m.a[i][j]<<" ";
55         }
56     }
57     cout<<endl<<n<<endl<<n;
58     return 0;
59 }
60

}

③关于高斯消元基础（noip不会考于t1t2）{

　　这个模板是用来解决n阶定方程的

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #define maxn 100
 6 using namespace std;
 7 int n,m,k,l,a,b,c;double mp[maxn][maxn];
 8 int main(){
 9     cin >> n;
10     for(int i = 1; i <= n; i ++)
11         for(int j = 1; j <= n + 1; j ++)
12             cin >> mp[i][j];   
13     for(int j = 1; j <= n; j ++){
14         int rgt = 0;
15         for(int i = j; i <= n; i ++)
16             if(mp[i][j]){rgt = i; break;}
17         if(!rgt)continue;
18         if(rgt ^ j)swap(mp[rgt],mp[j]);
19         
20         for(int i = j + 1; i <= n; i ++){
21             double div = mp[i][j] / mp[j][j];
22             for(int k = 1; k <= n + 1; k ++)mp[i][k] -= div*mp[j][k];
23         }
24     }
25     for(int j = n; j >= 1; j --){
26         if(mp[j][j] == 0){cout<<"No Solution"; return 0;}
27         mp[j][n+1] =  mp[j][n+1] / mp[j][j];
28         for(int i = j-1; i >= 1; i --)mp[i][n+1] -= mp[j][n+1] * mp[i][j];
29     }
30     for(int i = 1; i <= n; i ++)printf("%.2lf\n" ,mp[i][n+1]);
31     return 0;
32 }

高斯消元还可以解决一些异或，异或这个东西跟加法很相似。

因为若 a+(1<<k)&&（a>>k)&1==0 这个时候更加一样，否则就是减。

我们发现高斯消元是on^3的，那么如果让跑1000之内的怎么办呢。

我们就需要一个玄学的东西叫做线型基！

这个东西是一个纯粹的省选算法，noip向了解即可。

}

④基本数列公式

{

1.等比数列求和

2.等差数列求和

3.等差数列性质

}

题目

1.P3938 斐波那契

2.P1306 斐波那契公约数

3.P1962 斐波那契数列

4.P1939 【模板】矩阵加速（数列）

5.T37388 P哥破解密码

　4.函数（积性函数初步）

①三分法{

用于求单峰函数的极值

我们发现如果取两个点（三分之一位置）mid1 mid2

会有三种情况（还有一种是相等，那时候任意都行）

mid1>mid2那么峰值不可能在mid2-r;

mid1<mid2峰值不可能在 l-mid1;

那么我们就会发现递推即可缩小lr

锁定峰值

洛谷搜索三分法有模板

 1 // luogu-judger-enable-o2
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<iostream>
 7 #include<queue>
 8 #define maxn 1000
 9 using namespace std;
10 double n,m,a,b,mid1,mid2,k[maxn];
11 double f(double x){
12     double ans;
13     ans=k[0];
14     for(int i=1;i<=n;i++){
15         ans+=pow(x,i)*k[i];    
16     }
17     return ans;
18 }
19 double sanfen(double l,double r){
20     if(r-l<0.000001)return l;
21     double mid1=(r-l)/3+l;
22     double mid2=r-(r-l)/3;
23     //cout<<f(mid1)<<" "<<f(mid2)<<endl;
24     if(f(mid1)>f(mid2))r=mid2;
25     else l=mid1;
26     return sanfen(l,r);
27 } 
28 int main(){
29     cin>>n>>a>>b;
30     
31     for(int i=n;i>=0;i--){
32         cin>>k[i];
33     }//cout<<f(a)<<" "<<f(b)<<endl; 
34     printf("%.5lf",sanfen(a,b));
35     return 0;
36 }

这个东西还可以处理凸壳（见计算几何）

}

② 欧拉函数

我在前面写了筛法，自己回去找吧

有用的性质（莫比乌斯反演证明出来的）(Σ（d|n）φ（d）)=n

中间的竖杠，整除的意思。

③莫比乌斯反演初步——这个noip如果考了 ccf就是疯了，真的！！！！！

做题可以看一个叫popoqqq的人的博客最底下。

5.概率论

考过不难没啥好总结的主要是推式子那就结束吧

省选数学有哪些内容呢？

哎，加油吧！

一维数学
exgcd，crt，excrt，gcd，bsgs，exbsgs，快速幂，龟速乘，哈希，MillerRabin，Ruben rho，线性筛积性函数，素数线性筛，欧拉公式，费马小定理，乘法逆元，欧拉函数优化快速幂，拉格朗日查值，莫比乌斯反演，fft/ntt，杜教筛，高斯函数化简，牛顿迭代，泰勒展开。
计算几何
凸包，半平面交，旋转卡壳，三分法，导数，定积分分析时间复杂度
组合数学(二维数学)
卢卡斯定理，拓展卢卡斯，matrixtree，高斯消元，异或方程，线性基，行列式求值，矩阵乘法，矩乘快速幂，递推数列特征根

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有