快考试了 是时候整理一下算法复习一下了 先从最弱的数论开始吧 ~ ~
1. 素数
首先是筛素数
根号n的不说了
埃不拉不拉筛O(Nlogn)
欧拉筛O(N) 好像好有个loglog来 忘记了总之快一点
其实埃筛的复杂度已经很优秀了
上面是预处理某个10^7-8范围内的全部素数的方法
#include<cstdio> #define maxn 22000 using namespace std; int l,r,cnt; bool f[maxn]; void Eprime(){ f[1]=f[0]=1; for(int i=2;i<=21000;i++)if(f[i]==0) for(int j=i+i;j<=21000;j+=i) f[j]=1; } int main() { scanf("%d%d",&l,&r); Eprime(); for(int i=l;i<=r;i++) if(f[i]==0)cnt++; printf("%d ",cnt); return 0; }
#include<cstdio> #define maxn 22000 using namespace std; int l,r,cnt,num,prime[maxn]; bool f[maxn]; void Oprime(){ for(int i=2;i<=21000;i++){ if(f[i]==0)prime[++num]=i; for(int j=1;j<=num;j++){ if(i*prime[j]>21000)break; f[i*prime[j]]=1; if(i%prime[j]==0)break; } } } int main() { scanf("%d%d",&l,&r); Oprime(); for(int i=1;i<=num;i++){ if(prime[i]>=l&&prime[i]<=r)cnt++; if(prime[i]>r)break; } printf("%d ",cnt); return 0; }
如果给你个大数 比如说超了int 判断素数
那么以上的方法就跑不出来了
我们用到另外两种判断素数的算法
(1) 费马小定理 复杂度(次数*logn)
若p为素数 则a^(p-1)%p=1
但是如果翻过来就不一定正确
优异类数叫做卡迈克尔数就是合数
但上面那个概率是很大的所以嘛
多生成几个a试试 一般出错的概率还是很小的
当然如果考试那天人品XX的话就怨不得谁了
#include<iostream> #include<cstdio> #include<cstdlib> #include<ctime> #define ll long long using namespace std; ll p,falg; ll mul(ll a,ll b){ a%=p;b%=p; ll r=0; while(b){ if(b&1){ b--;r+=a;r%=p; } a<<=1;a%=p;b>>=1; } return r%p; } ll qm(ll a,ll b){ ll r=1; while(b){ if(b&1)r=mul(r,a); b>>=1;a=mul(a,a); } return r; } int main() { cin>>p;srand(time(0)); for(int i=1;i<=15;i++){ int a=rand()%(p-1)+1; int x=qm(a,p-1); if(x!=1){ falg=1;break; } } if(falg)cout<<"No"<<endl; else cout<<"Yes"<<endl; }
(2)Miller Rabin 复杂度(logn)好像还有个常熟 不过无伤大雅
再说说误判概率 经过k轮这玩意 将合数误判为素数的概率是(1/4)^k
素数误判为合数的概率是0 一般进行个10轮15轮就好了
要是这样的概率都给碰上了那就没啥可说的了....
下面说说算法过程
首先 2特判一下子 对于剩下的奇素数
有 fermat a^(p-1)%p=1
避免出错同时加速这个算法
另一个定理 若x&1,且x*x%p==1 则有x=1或x=-1(即x==p-1)
把p-1写成p-1=m*2^j 然后呢 j次测试 若不满足上面那个东西 直接肯定p不是prime
每次都乘回来 最后又得到了p-1 再来一次fermat就ok了
很不错的算法 Orz谁想出来的
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<ctime> #define ll long long using namespace std; ll p; ll mul(ll a,ll b){ a%=p;b%=p; ll r=0; while(b){ if(b&1){ b--;r+=a;r%=p; } a<<=1;a%=p;b>>=1; } return r%p; } ll qm(ll a,ll b){ ll r=1; while(b){ if(b&1)r=mul(r,a); b>>=1;a=mul(a,a); } return r; } bool Miller_Rabin(){ if(p<=2)return 1; if(p%2==0)return 0; ll x,y,m,k=0,T=15,a; m=p-1; while(m%2==0){ k++;m>>=1; } while(T--){ a=rand()%(p-1)+1; x=qm(a,m); for(ll i=1;i<=k;i++){ y=mul(x,x); if(y==1&&x!=1&&x!=p-1)return 0; x=y; } if(x!=1)return 0; } return 1; } int main() { cin>>p; if(Miller_Rabin())printf("Yes "); else printf("No "); return 0; }
2. 质因数分解
这个吗 一般算法的复杂度是够用的
当然如果筛素数的话会快 而且对于一个质数 可以直接返回
当然如果对n!每个数质因数分解的话那筛素数就快多了
当然我们还有别的方法 忘记叫什么名字了 咨询的数竞的孩子
n!里p的个数(p为素数)=n/p+n/(p*p)+n/(p*p*p)+n/(p*p*p*p)...(p*p*..)<=n
这样就快得多了 有时排列组合可以用到这个
/* 然后身边学过数竞的孩子说求阶乘里有几个素数有别的方法 n!里p的个数=n/p+n/p*p+n/p*p*p.....知道p==n 知道这个就快了嘛 嗖嗖的..... */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1000010 #define ll long long using namespace std; ll n,m,p,a[maxn],x,y,ans=1,prime[maxn],num,P[maxn]; bool f[maxn]; void Get(){ for(int i=2;i<=1000000;i++){ if(f[i]==0)prime[++num]=i,P[i]=num; for(int j=1;j<=num;j++){ if(i*prime[j]>1000000)break; f[i*prime[j]]=1; if(i%prime[j]==0)break; } } } ll qm(ll a,ll b,ll c){ ll r=1; while(b){ if(b&1)r*=a,r%=c; b>>=1;a*=a;a%=c; } return r; } int main() { freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); cin>>n>>m>>p;Get(); for(int i=1;i<=num;i++){ ll P=prime[i]; while(P<=n){ a[i]+=n/P; P*=prime[i]; } } for(int i=1;i<=num;i++){ ll P=prime[i]; while(P<=m){ a[i]-=m/P; P*=prime[i]; } } for(int i=1;i<=num;i++){ ll P=prime[i]; while(P<=n-m){ a[i]-=(n-m)/P; P*=prime[i]; } } for(int i=1;i<=num;i++) ans=ans*qm(prime[i],a[i],p)%p; cout<<ans<<endl; return 0; }
3. 卡特兰数 f(n)=f(n-1)*(4*n-2)/(n+1)
感觉这就是个bug 费劲写出来的dp
结果发现想到卡特兰数的几行就搞完了
QAQ
有许多典型的问题(先背过23333)
比如说 给定1-n问出栈序列的种类数
一个有n个结点的二叉树总共有多少种形态
在一个圆上2*K个不同的结点连K条线段，
每个结点用一次将圆分成最少部分的前提下有多少种连线的方法
n对括号有多少种匹配方式
矩阵链乘
求一个凸多边形区域划分成三角形区域的方法数
.......
比较多的例子 可以自己搜搜
其实原理都差不多的样子
那矩阵链乘说吧 P=a1×a2×a3×……×an +括号 有几种方法
可以这样考虑，首先通过括号化，将P分成两个部分，然后分别对两个部分进行括号化。
比如分成(a1)×(a2×a3.....×an)，然后再对(a1)和(a2×a3.....×an)分别括号化；
又如分成(a1×a2)×(a3.....×an)，然后再对(a1×a2)和(a3.....×an)括号化。
f(n) = f(1)*f(n-1) + f(2)*f(n-2) + f(3)*f(n-3) + f(n-1)*f(1)。
手写一下的话 就是卡特兰数
4. 欧拉函数
定义：设n为正整数 不大于n的且与n互素的整数个数记为f(n)
求欧拉函数的方法
首先暴力好打 慢
f(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)... pi为n的质因子
那就要分解质因数了 好办
应用嘛 还是比较好使的
求逆元
定义应用
a^(f(p))%p=1
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; ll n,ans; ll init() { ll x=0;char s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } int main() { while(1) { n=init(); if(n==0)break; ans=n; for(ll i=2;i*i<=n;i++) if(n%i==0) { while(n%i==0)n/=i; ans=ans/i*(i-1); } if(n>1)ans=ans/n*(n-1); printf("%ld ",ans); } return 0; }
5. 排列组合
一般比较好打 关键是能不能看出来 能不能写出公式
C(N,M)=N!/(M!*(N-M)!)
如果%p的话 要是p为素数 就可以搞一下逆元(欧拉函数 gcd都可以)
要是p不是素数 就比较蛋疼了 反正求逆元就是各种错...
质因数分解 然后把分母都给抹了去
要是nm很大很大怎么办呢(%p 且p为素数)
用卢卡斯定理 这是个好东西啊
定义：设p为素数 将非负整数ab表示成p进制
a=ak*p^k+a(k-1)*p^(k-1)+...+a1*p+a0 b同理
允许首位为0 且b<a
则 C(a,b)同余C(ak,bk)*C(a(k-1),b(k-1))*...*C(a0,b0)(mod p)
证明嘛 不会啊23333 可以抓个数竞的孩子问问23333
写代码也是很好写的
#include<iostream> #include<cstdio> #include<cstring> #define maxn 100010 #define ll long long using namespace std; ll T,n,m,p,f[maxn]; void Get(){ f[0]=1; for(int i=1;i<=p;i++) f[i]=f[i-1]*i%p; } ll qm(ll a,ll b){ a%=p;ll r=1; while(b){ if(b&1)r=r*a%p; b>>=1;a=a*a%p; } return r; } ll C(ll a,ll b){ if(b>a)return 0; return f[a]*qm(f[b]*f[a-b],p-2)%p; } ll Lcs(ll a,ll b){ if(b==0)return 1; return C(a%p,b%p)*Lcs(a/p,b/p)%p; } int main() { cin>>T; while(T--){ memset(f,0,sizeof(f)); cin>>n>>m>>p;Get(); cout<<Lcs(n+m,n)<<endl; } return 0; }
6. 欧几里得 扩展欧几里得(裴蜀定理)
这个东西用的比较多吧还算是
首先gcd本质就是把两个数质因数分解
然后每个素数的指数取小lcm是取大
欧几里得就是辗转相除法 有库函数但是略慢
扩展欧几里得用来解不定方程 或者求逆元
也可以解mod方程 比如a%p=1 -> ax-bp=1
算法过程 解ax+by=c 实际上解得是ax+by=gcd(a,b)
然后两边都*gcd/c 这样得到一组基解
调整的话 保证等式成立的前提下 x+b/gcd y-a/gcd 或者反过来
可以得到最小正整数解
/*搞个题目做做 poj 1061*/ #include<iostream> #include<cstdio> #include<cstring> #define mod(a,b) (a%b+b)%b #define ll long long using namespace std; ll x,y,g,n,m,l,k; void gcd(ll a,ll b){ if(b==0){ x=1;y=0;g=a;return; } gcd(b,a%b); ll tmp=x;x=y;y=tmp-a/b*y; } int main() { cin>>x>>y>>m>>n>>l; ll a=mod(m-n,l),b=l,c=mod(y-x,l); gcd(a,b); if(c%g){cout<<"Impossible"<<endl;return 0;} x=x*c/g;k=b/g;x=mod(x,k); cout<<x<<endl; return 0; }
7. mod运算
支持+-* /的话要搞搞逆元在*上去
8. 快速幂
很简单的 不详细写了
最近转非递归了 快点
9. 矩阵乘法
这玩意还是很好使的
用于解决线性递推式的计算 复杂度logn
手推一个矩阵 还有一个记答案
注意要是递推式里有与n有关的东西 就会比较麻烦
矩阵好好搞搞
还有就是dp优化了
当然还有许多许多用处 网上都能搜到
/*codevs 2314 矩阵乘法 分块写*/ #include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; ll n,p,a[3][3],f[3][3]; ll Get(ll x){ ll r=0; while(x)r++,x/=10; return r; } ll Pow(ll x){ ll r=1; for(int i=1;i<=x;i++) r=r*10; return r; } ll slow(ll a,ll b){ a%=p;b%=p; ll r=0; while(b){ if(b&1)r+=a,r%=p,b--; a<<=1;b>>=1;a%=p; } return r; } void mul(ll a[3][3],ll b[3][3]){ ll c[3][3]={0}; for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) c[i][j]=(c[i][j]+slow(a[i][k],b[k][j]))%p; for(int i=0;i<3;i++) for(int j=0;j<3;j++) a[i][j]=c[i][j]; } ll Cal(ll x,ll l,ll r){ ll c=r-l; x=slow(x,l);x=(x*10%p+l)%p;//慢乘慢乘慢乘 写丑了 这个应该不用特判或许 //x=(x*l%p*10%p+l)%p; memset(a,0,sizeof(a)); memset(f,0,sizeof(f)); f[0][0]=x;f[0][1]=l;f[0][2]=1; a[0][0]=l*10%p;a[1][0]=a[1][1]=a[2][0]=a[2][1]=a[2][2]=1; while(c){ if(c&1)mul(f,a); c>>=1;mul(a,a); } return f[0][0]; } int main() { cin>>n>>p;ll x=0; ll len=Get(n); for(int i=1;i<len;i++) x=Cal(x,Pow(i-1),Pow(i)-1); x=Cal(x,Pow(len-1),n); cout<<x<<endl; return 0; }
10. 中国剩余定理
解一次同余方程组
mi模数 bi为余数
s=Σmi Mi=s/mi
X=Σ(Mi*bi*Mi的逆元)%s
X是基解 步长为s
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; ll n,l,r,b[11],m[11],M[11],Mi[11],s=1,ans,sum,x,y; void E_gcd(ll a,ll b) { if(!b){x=1;y=0;return;} E_gcd(b,a%b);int tmp=x;x=y;y=tmp-a/b*y; } int main() { cin>>n>>l>>r; for(int i=1;i<=n;i++) cin>>m[i]>>b[i],s*=m[i]; for(int i=1;i<=n;i++) M[i]=s/m[i]; for(int i=1;i<=n;i++) { x=y=0; E_gcd(M[i],m[i]); Mi[i]=(x+m[i])%m[i]; } for(int i=1;i<=n;i++) ans=(ans+M[i]*Mi[i]%s*b[i])%s; if(ans<l||ans>r)ans=sum=0; else sum=(r-ans)/s+1; cout<<sum<<endl<<ans; return 0; }
11. 容斥原理
公式好长的不写了
一般把问题的并(不好求的)转化成问题的和-问题的交