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

各种数论模板不断更新绝对精品

2018-06-17 22:46:20来源：未知阅读 ()

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     else
11     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.扩展欧几里得求同余方程ax ≡ 1 (mod b)

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 }

扩展欧几里得求同余方程

3.扩展欧几里得求线性同余方程ax ≡ c (mod b)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 int x,y;
 6 int gcd(int a,int b)
 7 {
 8     if(b==0)
 9     return a;
10     else 
11     return gcd(b,a%b);
12 }
13 int exgcd(int a,int b,int &x,int &y)
14 {
15     if(b==0)
16     {
17         x=1;
18         y=0;
19         return a;
20     }
21     int r=exgcd(b,a%b,x,y);
22     int tmp=x;
23     x=y;
24     y=tmp-(a/b)*y;
25     return r;
26 }
27 int main()
28 {
29     int a,b,c;
30     scanf("%d%d%d",&a,&b,&c);
31     int y=gcd(a,b);
32     if(c%y!=0)
33     {
34         printf("No Answer");
35         return 0;
36     }
37     exgcd(a,b,x,y);
38     while(x<0)
39     {
40         x=x+b;
41     }
42     x=x*c;
43     printf("%d",x);
44     return 0;
45 }

扩展欧几里得求线性同余方程

4.求排列数

　　（1）基本排列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int f(int n)
 6 {
 7     if(n==0)return 1;
 8     else return n*f(n-1);
 9 }
10 int main()
11 {
12     int n,m;
13     scanf("%d%d",&n,&m);
14     printf("%d",f(n)/f(n-m));
15     return 0;
16 }

求排列数

　　（2）圆排列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int f(int n)
 6 {
 7     if(n==0)return 1;
 8     else return n*f(n-1);
 9 }
10 int main()
11 {
12     int n,m;
13     scanf("%d%d",&n,&m);
14     printf("%d",f(n)/(f(n-m)*m));
15     return 0;
16 }

圆排列

　　（3）全排列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int f(int n)
 6 {
 7     if(n==0)return 1;
 8     else return n*f(n-1);
 9 }
10 int main()
11 {
12     int n,m;
13     scanf("%d%d",&n,&m);
14     printf("%d",f(n));
15     return 0;
16 }

全排列

　　（4）项链排列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int f(int n)
 6 {
 7     if(n==0)return 1;
 8     else return n*f(n-1);
 9 }
10 int main()
11 {
12     int n;
13     scanf("%d",&n);
14     if(n==1||n==2)
15     printf("1");
16     else
17     printf("%d",f(n-1)/2);
18     return 0;
19 }

项链排列

5.求组合数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int f(int n)
 6 {
 7     if(n==0)return 1;
 8     else return n*f(n-1);
 9 }
10 int main()
11 {
12     int n,m;
13     scanf("%d%d",&n,&m);
14     printf("%d",f(n)/(f(m)*(n-m)));
15     return 0;
16 }

求组合数

6.快速幂

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio> 
 4 using namespace std;
 5 int fastpow(int a,int b)
 6 {
 7     int r=1;
 8     int base=a;
 9     while(b!=0)
10     {
11         if(b%2!=0)
12         r=r*base;
13         base=base*base;
14         b=b/2;
15     }
16     return r;
17 }
18 int main()
19 {
20     int a,b;
21     scanf("%d%d",&a,&b);
22     printf("%d",fastpow(a,b));
23     return 0;
24 }

快速幂

7.斐波那契数列

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 using namespace std;
 5 int main()
 6 {
 7     int n;
 8     scanf("%d",&n);
 9     double x=sqrt(5.0);
10     int ans=( pow ( ( ( 1+x ) / 2.0 ) , n ) / x - pow ( ( ( 1 - x ) / 2.0 ), n ) /x);
11     printf("%d",ans);
12     return 0;
13 }

通项公式

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 using namespace std;
 5 int a[10001];
 6 int main()
 7 {
 8     int n;
 9     a[1]=1;
10     a[2]=1;
11     scanf("%d",&n);
12     for(int i=3;i<=n;i++)
13     {
14         a[i]=a[i-1]+a[i-2];
15     }
16     cout<<a[n];
17     return 0;
18 }

递推

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 using namespace std;
 5 int a[10001];
 6 int f(int n)
 7 {
 8     if(n==1||n==2)return 1;
 9     else return f(n-1)+f(n-2);
10 }
11 int main()
12 {
13     int n;
14     a[1]=1;
15     a[2]=1;
16     scanf("%d",&n);
17     printf("%d",f(n));
18     return 0;
19 }

递归

8.求二元一次不定方程

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 int x,y;
 6 int gcd(int a,int b)
 7 {
 8     if(b==0)
 9     return a;
10     else 
11     return gcd(b,a%b);
12 }
13 int exgcd(int a,int b,int &x,int &y)
14 {
15     if(b==0)
16     {
17         x=1;
18         y=0;
19         return a;
20     }
21     int r=exgcd(b,a%b,x,y);
22     int tmp=x;
23     x=y;
24     y=tmp-(a/b)*y;
25     return r;
26 }
27 int main()
28 {
29     int a,b,c;
30     scanf("%d%d%d",&a,&b,&c);
31     int y=gcd(a,b);
32     if(c%y!=0)
33     {
34         printf("No Answer");
35         return 0;
36     }
37     exgcd(a,b,x,y);
38     while(x<0)
39     {
40         x=x+b;
41         y=y+b;
42     }
43     x=x*c;
44     printf("%d %d",x,y);
45     return 0;
46 }

二元一次不定方程

9.欧拉定理

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<stack>
 5 using namespace std;
 6 stack<double>s;
 7 int main()
 8 {
 9     int n;
10     scanf("%d",&n);
11     int ll=n;
12     for(int i=2;i<=n-1;i++)
13     {
14         if(ll%i==0)
15         {
16             s.push(i);
17             while(ll%i==0)
18             ll=ll/i;
19         }
20     }
21     double ans=n;
22     while(s.size()!=0)
23     {
24         double p=s.top();
25         s.pop();
26         ans=ans*(double)(1.0-1.0/p);
27     }
28     printf("%.3lf",ans);
29     return 0;
30 }

欧拉定理

10.威尔逊定理判定素数

感觉把这个定理玩坏了。。因为它只能判断n<=35......。。。。比暴力都弱。。。。。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio> 
 4 #include<cmath>
 5 using namespace std;
 6 long long int f(int p)
 7 {
 8     if(p==0)
 9     return 1;
10     else return p*f(p-1);
11 }
12 int main()
13 {
14     int n;
15     scanf("%d",&n);
16     long long int ans=f(n-1);
17     if(ans%n==n-1)
18     printf("YES");
19     else 
20     printf("NO");
21     return 0;
22 }

威尔逊定理（判定素数）

11.Catalan数

 1 #include<iostream>
 2 using namespace std;
 3 long long int f[1001];
 4 int main()
 5 {
 6     int n;
 7     f[2]=1;
 8     f[3]=1;
 9     cin>>n;
10     n=n+2;
11     for(int i=4;i<=n;i++)
12     {
13         for(int j=2;j<=n-1;j++)
14         {
15             f[i]=f[j]*f[i-j+1]+f[i];
16         }
17     }
18     cout<<f[n];
19     return 0;
20 }

Catalan数

12.Stirling斯特林数

　　（1）第一类（旧noi放苹果问题）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 int t;
 7 int n;
 8 int m; 
 9 int tot=0;
10 int f(int a,int b)
11 {
12     if(a<=1||b<=1)
13     return 1;
14     if(a<b)
15     return f(a,a);
16     else 
17     return f(a,b-1)+f(a-b,b);
18  } 
19 int main()
20 {
21 
22     cin>>t;
23     for(int i=1;i<=t;i++)
24     {
25         cin>>m>>n;
26         cout<<f(m,n)<<endl;
27     } 
28     return 0; 
29 }

第一类斯特林数

　　（2）第二类

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 int t;
 7 int n;
 8 int m; 
 9 int tot=0;
10 int f(int a,int b)
11 {
12     if(a<=1||b<=1)
13     return 1;
14     if(a<b)
15     return f(a,a);
16     else 
17     return f(a-1,b-1)+f(a-1,b)*b;
18  } 
19 int main()
20 {
21 
22     cin>>t;
23     for(int i=1;i<=t;i++)
24     {
25         cin>>m>>n;
26         cout<<f(m,n)<<endl;
27      } 
28     return 0; 
29 }

第二类斯特林数

13.判断素数的常用方法

　　（1）暴力：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const int MAXN=10000001;
 6 int vis[MAXN];
 7 int bc[MAXN];
 8 int now=1;
 9 int pd(int n)
10 {
11     for(int i=2;i<=sqrt(n);i++)
12     {
13         if(n%i==0)
14         return 0;
15     }
16     return 1;
17 }
18 int main()
19 {
20     int m,n;
21     scanf("%d",&n);
22         if(pd(n)==1)
23         {
24             printf("YES");
25         }
26         else
27         {
28             printf("NO");
29         }
30     return 0;
31 }

暴力求素数

　　（2）线性筛法

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const int MAXN=100000001;
 6 int vis[MAXN];
 7 int main()
 8 {
 9     int n;
10     scanf("%d",&n);
11     for(int i=2;i<=sqrt(n);i++)
12     {
13         if(vis[i]==0)
14         {
15             for(int j=i*i;j<=n;j=j+i)
16             {
17                 vis[j]=1;
18             }
19         }
20     }
21     if(vis[n]==0)
22     {
23         printf("Yes");
24     }
25     else 
26     {
27         printf("No");
28     }
29     return 0;
30  }

线性筛法求素数

　　（3）费马小定理（高能算法）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<ctime>
 6 #define ll long long int
 7 using namespace std;
 8 ll n;
 9 ll pd[14]={10,35,77,535,71497,2,3,5,7,11,3161};
10 ll fastmul(ll a,ll b)
11 {
12     ll r=0;
13     ll base=a;
14     while(b!=0)
15     {
16         if(b%2!=0)
17         {
18             b--;
19             r=(r+base)%n;
20         }
21         b=b/2;
22         base=(base+base)%n;
23     }
24     return r%n;
25 }
26 ll fastpow(ll a,ll b)
27 {
28     ll r=1;
29     ll base=a;
30     while(b!=0)
31     {
32         if(b%2!=0)
33         r=fastmul(r,base)%n;
34         base=fastmul(base,base)%n;
35         b=b/2;
36     }
37     return r%n;
38 }
39 ll check(ll n)
40 {
41     if(n==2)
42     {
43         return 1;
44     }
45     if(n<2&&(n%2==0))
46     {
47         return 0;
48     }
49     for(ll i=0;i<11;i++)
50     {
51         ll x=pd[i];
52         if(x%n==0)
53         continue;
54         ll ans=fastpow(x,n-1)%n;
55         if(ans!=1)
56         return 0;
57     }
58     return 1;
59 }
60 int main()
61 {
62     //srand(time(0));
63     //scanf("%lld",&n);
64     cin>>n;
65     for(int i=1;i<=n;i++)
66     {
67         if(check(i))
68         {
69             printf("%d\n",i);
70         }
71     }
72     
73     return 0;
74 }

费马小定理判断素数

　　（4）威尔逊定理判定素数（基本可以无视）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio> 
 4 #include<cmath>
 5 using namespace std;
 6 long long int f(int p)
 7 {
 8     if(p==0)
 9     return 1;
10     else return p*f(p-1);
11 }
12 int main()
13 {
14     int n;
15     scanf("%d",&n);
16     long long int ans=f(n-1);
17     if(ans%n==n-1)
18     printf("YES");
19     else 
20     printf("NO");
21     return 0;
22 }
23 
24 威尔逊定理（判定素数）

威尔逊定理求素数

14.筛法求欧拉函数（[SDOI2008]仪仗队）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=100001;
 7 int euler[MAXN];
 8 int ans=1;
 9 int main()
10 {
11     int n;
12     scanf("%d",&n);
13     n--;
14     euler[1]=1;
15     for(int i=2;i<=n;i++)
16         euler[i]=i;
17     for(int i=2;i<=n;i++)
18     {
19         if(euler[i]==i)
20             for(int j=i;j<=n;j+=i)
21                 euler[j]=euler[j]/i*(i-1);
22         ans+=euler[i];
23     }
24     printf("%d",ans*2+1);
25     return 0;
26 }