首页 > 代码库 > 数论基础模板
数论基础模板
以前写的几个数论模板，整整吧，反正数论这么弱貌似只会gcd的样子...
来，先来gcd
1.
gcd与lcm
#include<iostream>#include<cstdio>using namespace std;int gcd(int a,int b){ if(b==0) return a; else return gcd(b,a%b);}int lcm(int x,int y){ return (x*y)/gcd(x,y);}int main(){ int a,b; scanf("%d%d",&a,&b); printf("%d %d",gcd(a,b),lcm(a,b)); return 0;}
扩展欧几里得
求解 x，y的方法的理解
设 a>b。
1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；
2，a>b>0 时
设 ax1+ by1= gcd(a,b);
bx2+ (a mod b)y2= gcd(b,a mod b);
根据朴素的欧几里得原理有 gcd(a,b) = gcd(b,a mod b);
则:ax1+ by1= bx2+ (a mod b)y2;
即:ax1+ by1= bx2+ (a - [a / b] * b)y2=ay2+ bx2- [a / b] * by2;
也就是ax1+ by1 == ay2+ b(x2- [a / b] *y2);
根据恒等定理得：x1=y2; y1=x2- [a / b] *y2;
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
2.ex-gcd
ex-gcd/*扩展欧几里得 ax%b==1 -> ax-by==1 求不定方程的一组解 使x为最小正整数解 */#include<iostream>#include<cstdio>#include<cstring>using namespace std;int x,y,gcd;int Extend(int a,int b){ if(b==0) { x=1;y=0; gcd=a; } else { Extend(b,a%b); int tmp=x; x=y; y=tmp-a/b*y; }}int main(){ int a,b; scanf("%d%d",&a,&b); Extend(a,-b); x=x*(1/gcd); if(x<0)while(x<0)x=x+b; else while(x-b>0)x=x-b; printf("%d\n",x); return 0;}
质因数分解
这个吗 一般算法的复杂度是够用的
当然如果筛素数的话会快 而且对于一个质数 可以直接返回
当然如果对n!每个数质因数分解的话那筛素数就快多了
当然我们还有别的方法 忘记叫什么名字了 咨询的数竞的孩子
n!里p的个数(p为素数)=n/p+n/(p*p)+n/(p*p*p)+n/(p*p*p*p)...(p*p*..)<=n
这样就快得多了 有时排列组合可以用到这个
3.分解单个数
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n;int a[10000];int main(){ scanf("%d",&n); printf("%d=",n); int cnt=0; for (int i=2;i<=n;i++) { while (n%i==0&&n) { a[cnt++]=i; n/=i; } } for (int i=0;i<cnt-1;i++) { printf("%d*",a[i]); } printf("%d\n",a[cnt-1]); return 0;}
4.阶乘分解
#include<iostream>#include<cstdio>#define maxn 5000010#define mod 100000007#define ll long longusing namespace std;ll n,prime[maxn/10],c[maxn/10],num,ans=1;bool f[maxn]; void Prime(){ for(int i=2;i<=n;i++) { if(f[i]==0)prime[++num]=i; for(int j=1;j<=num;j++){ if(i*prime[j]>maxn-10)break; f[i*prime[j]]=1; if(i%prime[j]==0)break; } }}void Solve(){ for(int i=1;i<=num;i++){ ll P=prime[i]; if(P>n)break; while(n>=P){ c[i]+=n/P;P*=prime[i]; } if(c[i]) printf("%d ",c[i]); }}int main(){ cin>>n; Prime();Solve(); return 0;}
快速幂
5.快速幂取模
#include<iostream>#include<cstdio>#define mod 1000000007using namespace std;int x,y;int main(){ scanf("%d%d",&x,&y); int r=1; while(y) { if(y&1) r=(long long)r*x%mod;//y&1 pan duan zhe yi wei shi fou shi yi y>>=1;x=(long long)x*x%mod; } printf("%d",r%mod); return 0;}
欧拉函数
定义：设n为正整数 不大于n的且与n互素的整数个数记为f(n)
求欧拉函数的方法
首先暴力好打 慢
f(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)... pi为n的质因子
那就要分解质因数了 好办
应用嘛 还是比较好使的
求逆元
定义应用
a^(f(p))%p=1
6.欧拉函数
#include<iostream>#include<cstdio>#include<cstring>#define ll long longusing 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\n",ans); } return 0;}
素数
7.欧拉筛
#include<cstdio>#define maxn 22000using namespace std;int l,r,cnt,num,prime[maxn];bool f[maxn];void Oprime(){ for(int i=2;i<=maxn;i++){ if(f[i]==0)prime[++num]=i; for(int j=1;j<=num;j++){ if(i*prime[j]>maxn)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\n",cnt); return 0;}
素数判定
(1)费马小定理
复杂度(次数*logn)
若p为素数 则a^(p-1)%p=1
但是如果翻过来就不一定正确
优异类数叫做卡迈克尔数就是合数
但上面那个概率是很大的所以嘛
多生成几个a试试 一般出错的概率还是很小的
当然如果考试那天人品XX的话就怨不得谁了
8.费马小定理
#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<ctime>#define ll long longusing namespace std;ll p,flag;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(){ ios::sync_with_stdio(false); cin>>p; if(p==1) { printf("No\n"); return 0; } if(p==2) { printf("Yes\n"); return 0; } 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) { flag=1; break; } } if(flag) { printf("No"); return 0; } else { printf("Yes"); return 0; } return 0;}
(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了
9.Miller Rabin
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<ctime>#define ll long longusing 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\n"); else printf("No\n"); return 0;}
表示还很弱很弱很弱，不会的还有很多很多很多.......
数论基础模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。