首页 > 代码库 > 各种数论模板
各种数论模板
1.筛法求素数
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=10001; 7 int vis[MAXN]; 8 int main() 9 {10 int n;11 scanf("%d",&n);12 for(int i=2;i<=sqrt(n);i++)13 {14 if(vis[i]==0)15 {16 for(int j=i*i;j<=n;j=j+i)17 {18 vis[j]=1;19 }20 }21 }22 for(int i=2;i<=n;i++)23 {24 if(vis[i]==0)25 printf("%d ",i);26 }27 return 0;28 }
2.欧几里得求最大公约数及最小公倍数
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int gcd(int x,int y) 7 { 8 if(y==0) 9 return x;10 else11 return gcd(y,x%y);12 }13 int main()14 {15 int x,y;16 scanf("%d%d",&x,&y);17 int gys=gcd(x,y); 18 printf("%d\n%d",gys,x*y/gys);19 20 return 0;21 }
3.扩展欧几里得求同余方程
http://codevs.cn/problem/1200/
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 using namespace std; 5 int x,y; 6 int exgcd(int a,int b,int &x,int &y) 7 { 8 if(b==0) 9 {10 x=1;11 y=0;12 return a;13 }14 int r=exgcd(b,a%b,x,y);15 int tmp=x;16 x=y;17 y=tmp-(a/b)*y;18 return r;19 }20 int main()21 {22 int a,b;23 scanf("%d%d",&a,&b);24 exgcd(a,b,x,y);25 while(x<0)26 x=x+b;27 printf("%d",x);28 return 0;29 }
各种数论模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。