首页 > 代码库 > 各种数论模板

各种数论模板

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 }
扩展欧几里得求同余方程

 

各种数论模板